IMHO the problem statement is misleading, since as its stated we aren't *quite* looking for maximal planar graphs. Consider the following input:
4 5
1 2
2 3
3 4
4 1
1 3
One way this can be interpreted is as a square with one of its diagonals connected. This is a planar embedding of a graph where no additional edge can be drawn, but however this graph is **not maximal**.
As stated, the problem is to determine whether there exists a maximal *embedding* of the given graph (if its planar of course), and not just determine if the graph itself is maximal. In fact I noticed a lot of the AC solutions miss the above case.