Graph planarity
In graph theory, the planarity testing problem is the algorithmic problem of testing whether a given graph is a planar graph (that is, whether it can be drawn in the plane without edge intersections). This is a well-studied problem in computer science for which many practical algorithms have emerged, many taking advantage of novel data structures. Most of these methods operate in O(n) time (linear time), where n is the number of edges (or vertices) in the graph, which is asymptotically optimal. Rather than just being a single Boolean value, the output of a planarity testing algorithm may be a planar graph embedding, if the graph is planar, or an obstacle to planarity such as a Kuratowski subgraph if it is not.
Planarity testing algorithms typically take advantage of theorems in graph theory that characterize the set of planar graphs in terms that are independent of graph drawings. These include
The Fraysseix–Rosenstiehl planarity criterion can be used directly as part of algorithms for planarity testing, while Kuratowski's and Wagner's theorems have indirect applications: if an algorithm can find a copy of K5 or K3,3 within a given graph, it can be sure that the input graph is not planar and return without additional computation.
Other planarity criteria, that characterize planar graphs mathematically but are less central to planarity testing algorithms, include Whitney's planarity criterion that a graph is planar if and only if its graphic matroid is also cographic, Mac Lane's planarity criterion characterizing planar graphs by the bases of their cycle spaces, Schnyder's theorem characterizing planar graphs by the order dimension of an associated partial order, and Colin de Verdière's planarity criterion using spectral graph theory.
...
Wikipedia