# CONPOIN - Editorial

#PROBLEM LINK:
[Practice][222]
[Contest][111]
**Author:** [Pavel Sheftelevich][3333]
**Tester:** [Mahbubul Hasan][4444] and [Sunny Aggarwal][5555]
**Editorialist:** [Balajiganapathi Senthilnathan][6666]
**Russian Translator:** [Sergey Kulik][7777]
**Mandarian Translator:** [Gedi Zheng][8888]
#DIFFICULTY:
Hard
#PREREQUISITES:
Maximal planar graph
#PROBLEM:
You are given N points and M edges connecting them. You have to determine whether it is possible to draw those N points and M edges on a plane such that no two edges intersect except at the endpoints and it is not possible to add another edge without intersecting an existing edge.
#EXPLANATION:
The first part is to find whether it is possible to draw the points and edges such that the edges are non intersecting. That is the definition of planar graph.
The second part of the condition is that if we add one more edge the graph will be non planar. Thus we have to find out whether the given graph is a *maximal planar graph* or not.
This can be done in linear time using the algorithm given [here][1].
#Time Complexity:
$O(N)$
#AUTHOR'S AND TESTER'S SOLUTIONS:
[Author's solution][55]
[Tester's solution][66]
[1]: https://www.researchgate.net/publication/220112472_A_simple_recognition_of_maximal_planar_graphs
[111]: http://www.codechef.com/COOK58/problems/CONPOIN
[222]: http://www.codechef.com/problems/CONPOIN
[3333]: ~~http://www.codechef.com/users/flying_ant
~~http://www.codechef.com/users/pavel1996
[4444]: ~~http://www.codechef.com/users/flying_ant
~~http://www.codechef.com/users/white_king
[5555]: ~~http://www.codechef.com/users/utkarsh_lath
~~http://www.codechef.com/users/ma5termind
[6666]: http://www.codechef.com/users/balajiganapath
[7777]: http://www.codechef.com/users/xcwgf666
[8888]: http://www.codechef.com/users/stzgd
[55]: ~~http://www.codechef.com/download/Solutions/COOK58/setter/CONPOIN.java
~~http://www.codechef.com/download/Solutions/JUNE15/setter/CONPOIN.java
[66]: ~~http://www.codechef.com/download/Solutions/COOK58/tester/CONPOIN.cpp~~http://www.codechef.com/download/Solutions/JUNE15/tester/CONPOIN.cpp