Kuratowski
G planar iff no subgraph is a subdivision of K_5 or K_3,3.
Advertisement
Wagner
Equivalent: no minor is K_5 or K_3,3.
Advertisement
Hopcroft-Tarjan
O(V+E) via DFS + path adding. Complex to implement.
PQ-trees
Booth-Lueker: alternative O(V+E) using PQ-trees for maintaining consecutive-arrangement constraints.