Planarity testing

From Wikipedia, the free encyclopedia

This is an old revision of this page, as edited by David Eppstein (talk | contribs) at 19:31, 4 August 2013 (remove two redundant categories). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

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 criteria

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, MacLane'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.

Algorithms

Path addition method

The classic path addition method of Hopcroft and Tarjan[1] was the first published linear-time planarity testing algorithm in 1974.

Vertex addition method

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(n2) method conceived by Lempel, Even and Cederbaum in 1967.[2] It was improved by Even and Tarjan, who found a linear-time solution for the s,t-numbering step,[3] 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.[4] This method was also extended to allow a planar embedding (drawing) to be efficiently computed for a planar graph.[5] 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.[6]

Edge addition method

In 2004, Boyer and Myrvold [7] 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 K5 or K3,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, de Mendez and Rosenstiehl[8][9]). See [10] 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.[11] The source code for the planarity test[12][13] and the extraction of multiple Kuratowski subdivisions[12] is publicly available. Algorithms that locate a Kuratowski subgraph in linear time in vertices were developed by Williamson in the 1980s.[14]

References

  1. ^ Hopcroft, John; Tarjan, Robert E. (1974), "Efficient planarity testing", Journal of the Association for Computing Machinery, 21 (4): 549–568, doi:10.1145/321850.321852.
  2. ^ Lempel, A.; Even, S.; Cederbaum, I. (1967), "An algorithm for planarity testing of graphs", in Rosenstiehl, P. (ed.), Theory of Graphs, New York: Gordon and Breach, pp. 215–232.
  3. ^ Even, Shimon; Tarjan, Robert E. (1976), "Computing an st-numbering", Theoretical Computer Science, 2 (3): 339–344, doi:10.1016/0304-3975(76)90086-4.
  4. ^ Boyer & Myrvold (2004), p. 243: “Its implementation in LEDA is slower than LEDA implementations of many other O(n)-time planarity algorithms.”
  5. ^ Chiba, N.; Nishizeki, T.; Abe, A.; Ozawa, T. (1985), "A linear algorithm for embedding planar graphs using PQ–trees", Journal of Computer and Systems Sciences, 30 (1): 54–76, doi:10.1016/0022-0000(85)90004-2.
  6. ^ Shih, W. K.; Hsu, W. L. (1999), "A new planarity test", Theoretical Computer Science, 223 (1–2): 179–191, doi:10.1016/S0304-3975(98)00120-0.
  7. ^ Boyer, John M.; Myrvold, Wendy J. (2004), "On the cutting edge: simplified O(n) planarity by edge addition" (PDF), Journal of Graph Algorithms and Applications, 8 (3): 241–273.
  8. ^ de Fraysseix, H.; Ossona de Mendez, P.; Rosenstiehl, P. (2006), "Trémaux Trees and Planarity", International Journal of Foundations of Computer Science, 17 (5): 1017–1030, doi:10.1142/S0129054106004248.
  9. ^ Brandes, Ulrik (2009), The left-right planarity test (PDF).
  10. ^ Boyer, John M.; Cortese, P. F.; Patrignani, M.; Battista, G. D. (2003), "Stop minding your P's and Q's: implementing a fast and simple DFS-based planarity testing and embedding algorithm", Proc. 11th Int. Symp. Graph Drawing (GD '03), Lecture Notes in Computer Science, vol. 2912, Springer-Verlag, pp. 25–36
  11. ^ Chimani, M.; Mutzel, P.; Schmidt, J. M. (2008), "Efficient extraction of multiple Kuratowski subdivisions", Proc. 15th Int. Symp. Graph Drawing (GD'07), Lecture Notes in Computer Science, vol. 4875, Sydney, Australia: Springer-Verlag, pp. 159–170.
  12. ^ a b http://www.ogdf.net
  13. ^ http://www.boost.org/doc/libs/1_40_0/libs/graph/doc/boyer_myrvold.html
  14. ^ Williamson, S. G. (1984), "Depth First Search and Kuratowski Subgraphs", Journal Association of Computing Machinery, 31: 681–693, doi:10.1145/1634.322451
Retrieved from "https://en.wikipedia.org/w/index.php?title=Planarity_testing&oldid=567149769"