3 ms·
No, graph planarity can be determined using Kuratowski's theorem, which essentially states that a graph is planar if and only if it doesn't contain K_{5} or K_{
by karlding 10y ago
No, graph planarity can be determined using Kuratowski's theorem, which essentially states that a graph is planar if and only if it doesn't contain K_{5} or K_{3, 3}.
I believe the planarity test algorithm has been improved, such that it can be done in O(n) using the edge addition method [1].
[1] http://www.drdobbs.com/planarity-by-edge-addition/184406070 http://www.drdobbs.com/planarity-by-edge-addition/184406070