Planarity testing

The classic path addition method of Hopcroft and Tarjan[1] was the first published linear-time planarity testing algorithm in 1974. An implementation of Hopcroft and Tarjan's algorithm is provided in the Library of Efficient Data types and Algorithms by Mehlhorn, Mutzel and Näher.[2][3][4] In 2012, Taylor[5] extended this algorithm to generate all permutations of cyclic edge-order for planar embeddings of biconnected components.

Vertex addition methods work by maintaining a data structure representing the possible embeddings of an induced subgraph of the given graph, and adding vertices one at a time to this data structure. These methods began with an inefficient O(n²) method conceived by Lempel, Even and Cederbaum in 1967.[6] It was improved by Even and Tarjan, who found a linear-time solution for the s,t-numbering step,[7] and by Booth and Lueker, who developed the PQ tree data structure. With these improvements it is linear-time and outperforms the path addition method in practice.[8] This method was also extended to allow a planar embedding (drawing) to be efficiently computed for a planar graph.[9] In 1999, Shih and Hsu simplified these methods using the PC tree (an unrooted variant of the PQ tree) and a postorder traversal of the depth-first search tree of the vertices.[10]

In 2004, John Boyer and Wendy Myrvold[11] developed a simplified O(n) algorithm, originally inspired by the PQ tree method, which gets rid of the PQ tree and uses edge additions to compute a planar embedding, if possible. Otherwise, a Kuratowski subdivision (of either K₅ or K_3,3) is computed. This is one of the two current state-of-the-art algorithms today (the other one is the planarity testing algorithm of de Fraysseix, Ossona de Mendez and Rosenstiehl[12][13]). See [14] for an experimental comparison with a preliminary version of the Boyer and Myrvold planarity test. Furthermore, the Boyer–Myrvold test was extended to extract multiple Kuratowski subdivisions of a non-planar input graph in a running time linearly dependent on the output size.[15] The source code for the planarity test[16][17] and the extraction of multiple Kuratowski subdivisions[16] is publicly available. Algorithms that locate a Kuratowski subgraph in linear time in vertices were developed by Williamson in the 1980s.[18]

A different method uses an inductive construction of 3-connected graphs to incrementally build planar embeddings of every 3-connected component of G (and hence a planar embedding of G itself).[19] The construction starts with K₄ and is defined in such a way that every intermediate graph on the way to the full component is again 3-connected. Since such graphs have a unique embedding (up to flipping and the choice of the external face), the next bigger graph, if still planar, must be a refinement of the former graph. This allows to reduce the planarity test to just testing for each step whether the next added edge has both ends in the external face of the current embedding. While this is conceptually very simple (and gives linear running time), the method itself suffers from the complexity of finding the construction sequence.

Planarity testing has been studied in the Dynamic Algorithms model, in which one maintains an answer to a problem (in this case planarity) as the graph undergoes local updates, typically in the form of insertion/deletion of edges. In the edge-arrival case, there is an asympotically tight inverse-Ackermann function update-time algorithm due to La Poutré,[20] improving upon algorithms by Di Battista, Tamassia, and Westbrook.[21][22][23] In the fully-dynamic case where edges are both inserted and deleted, there is a logarithmic update-time lower bound by Pătrașcu and Demaine,[24] and a polylogarithmic update-time algorithm by Holm and Rotenberg,[25] improving on sub-linear update-time algorithms by Eppstein, Galil, Italiano, Sarnak, and Spencer.[26][27]