planarity testing
{{short description|Algorithmic problem of finding non-crossing drawings}}
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
- Kuratowski's theorem that a graph is planar if and only if it does not contain a subgraph that is a subdivision of K5 (the complete graph on five vertices) or K3,3 (the utility graph, a complete bipartite graph on six vertices, three of which connect to each of the other three).
- Wagner's theorem that a graph is planar if and only if it does not contain a minor (subgraph of a contraction) that is isomorphic to K5 or K3,3.
- The Fraysseix–Rosenstiehl planarity criterion, characterizing planar graphs in terms of a left-right ordering of the edges in a depth-first search tree.
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.
Algorithms
=Path addition method=
The classic path addition method of Hopcroft and Tarjan{{citation
| last1 = Hopcroft | first1 = John | author1-link = John Hopcroft
| last2 = Tarjan | first2 = Robert E. | author2-link = Robert Tarjan
| doi = 10.1145/321850.321852
| issue = 4
| journal = Journal of the Association for Computing Machinery
| pages = 549–568
| title = Efficient planarity testing
| volume = 21
| year = 1974 | hdl = 1813/6011
| s2cid = 6279825 | hdl-access = free
}}. 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.{{citation
| last1 = Mehlhorn | first1 = Kurt | author1-link = Kurt Mehlhorn
| last2 = Mutzel | first2 = Petra | author2-link = Petra Mutzel
| journal = Algorithmica
| pages = 233–242
| title = On the Embedding Phase of the Hopcroft and Tarjan Planarity Testing Algorithm
| volume = 16
| issue = 2
| year = 1996
| doi=10.1007/bf01940648| hdl = 11858/00-001M-0000-0014-B51D-B
| s2cid = 10014462
| url = https://kups.ub.uni-koeln.de/54688/1/zpr94-162.pdf | hdl-access = free
| last1 = Mehlhorn | first1 = Kurt | author1-link = Kurt Mehlhorn
| last2 = Mutzel | first2 = Petra | author2-link = Petra Mutzel
| last3 = Näher | first3 = Stefan
| title = An Implementation of the Hopcroft and Tarjan Planarity Test and Embedding Algorithm
| year = 1993}}{{citation
| last1 = Mehlhorn | first1 = Kurt | author1-link = Kurt Mehlhorn
| last2 = Näher | first2 = Stefan
| title = LEDA: A library of efficient data types and algorithms
| journal = Communications of the ACM
| volume = 38
| issue = 1
| pages = 96–102
| year = 1995| doi = 10.1145/204865.204889
| citeseerx = 10.1.1.54.9556
| s2cid = 2560175
}} In 2012, Taylor{{cite thesis
| type = Ph.D.
| last = Taylor |first=Martyn G.
| date = 2012
| title = Planarity Testing by Path Addition
| publisher = University of Kent
| url = http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.580367
| archive-url = https://web.archive.org/web/20160305074643/http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.580367
| archive-date = 2016-03-05
| url-status = live}} [https://archive.org/details/PlanarityTestingByPathAddition Alt URL] extended this algorithm to generate all permutations of cyclic edge-order for planar embeddings of biconnected components.
=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.{{citation
| last1 = Lempel | first1 = A. | author1-link = Abraham Lempel
| last2 = Even | first2 = S. | author2-link = Shimon Even
| last3 = Cederbaum | first3 = I.
| contribution = An algorithm for planarity testing of graphs
| editor-last = Rosenstiehl | editor-first = P.
| location = New York
| pages = 215–232
| publisher = Gordon and Breach
| title = Theory of Graphs
| year = 1967}}. It was improved by Even and Tarjan, who found a linear-time solution for the s,t-numbering step,{{citation
| last1 = Even | first1 = Shimon | author1-link = Shimon Even
| last2 = Tarjan | first2 = Robert E. | author2-link = Robert Tarjan
| doi = 10.1016/0304-3975(76)90086-4
| issue = 3
| journal = Theoretical Computer Science
| pages = 339–344
| title = Computing an st-numbering
| volume = 2
| year = 1976| doi-access = free
}}. 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.{{harvtxt|Boyer|Myrvold|2004}}, p. 243: “Its implementation in LEDA is slower than LEDA implementations of many other O(n)-time planarity algorithms.” This method was also extended to allow a planar embedding (drawing) to be efficiently computed for a planar graph.{{citation
| last1 = Chiba | first1 = N.
| last2 = Nishizeki | first2 = T. | author2-link = Takao Nishizeki
| last3 = Abe | first3 = A.
| last4 = Ozawa | first4 = T.
| doi = 10.1016/0022-0000(85)90004-2
| issue = 1
| journal = Journal of Computer and System Sciences
| pages = 54–76
| title = A linear algorithm for embedding planar graphs using PQ–trees
| volume = 30
| year = 1985| doi-access = free
}}. 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.{{citation
| last1 = Shih | first1 = W. K.
| last2 = Hsu | first2 = W. L.
| doi = 10.1016/S0304-3975(98)00120-0
| issue = 1–2
| journal = Theoretical Computer Science
| pages = 179–191
| title = A new planarity test
| volume = 223
| year = 1999| doi-access = free
}}.
=Edge addition method=
In 2004, John Boyer and Wendy Myrvold{{citation
| last1 = Boyer | first1 = John M.
| last2 = Myrvold | first2 = Wendy J. | author2-link = Wendy Myrvold
| issue = 3
| journal = Journal of Graph Algorithms and Applications
| pages = 241–273
| title = On the cutting edge: simplified O(n) planarity by edge addition
| url = http://jgaa.info/accepted/2004/BoyerMyrvold2004.8.3.pdf
| volume = 8
| year = 2004
| doi=10.7155/jgaa.00091| doi-access = free
}}. 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, Ossona de Mendez and Rosenstiehl{{citation
| last1 = de Fraysseix | first1 = H.
| last2 = Ossona de Mendez | first2 = P. | author2-link = Patrice Ossona de Mendez
| last3 = Rosenstiehl | first3 = P. | author3-link = Pierre Rosenstiehl
| journal = International Journal of Foundations of Computer Science
| pages = 1017–1030
| title = Trémaux Trees and Planarity
| volume = 17
| year = 2006
| doi = 10.1142/S0129054106004248
| issue = 5| arxiv = math/0610935| bibcode = 2006math.....10935D
| s2cid = 40107560
}}.{{citation|url=http://www.uni-konstanz.de/algo/publications/b-lrpt-sub.pdf|first=Ulrik|last=Brandes|author-link=Ulrik Brandes|title=The left-right planarity test|year=2009}}.). See {{citation
| last1 = Boyer | first1 = John M.
| last2 = Cortese | first2 = P. F.
| last3 = Patrignani | first3 = M.
| last4 = Battista | first4 = G. D.
| contribution = Stop minding your P's and Q's: implementing a fast and simple DFS-based planarity testing and embedding algorithm
| pages = 25–36
| publisher = Springer-Verlag
| series = Lecture Notes in Computer Science
| title = Proc. 11th Int. Symp. Graph Drawing (GD '03)
| volume = 2912
| year = 2003| title-link = International Symposium on Graph Drawing
}} 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.{{cite book
| last1 = Chimani | first1 = M.
| last2 = Mutzel | first2 = P. | author2-link = Petra Mutzel
| last3 = Schmidt | first3 = J. M.
| chapter = Efficient extraction of multiple Kuratowski subdivisions
| location = Sydney, Australia
| pages = 159–170
| publisher = Springer-Verlag
| series = Lecture Notes in Computer Science
| title = Proc. 15th Int. Symp. Graph Drawing (GD'07)
| volume = 4875
| year = 2008| title-link = International Symposium on Graph Drawing
| doi = 10.1007/978-3-540-77537-9_17
| isbn = 978-3-540-77536-2
}}. The source code for the planarity test{{Cite web | url=http://www.ogdf.net | title=OGDF - Open Graph Drawing Framework: Start}}{{Cite web | url=http://www.boost.org/doc/libs/1_40_0/libs/graph/doc/boyer_myrvold.html | title=Boost Graph Library: Boyer-Myrvold Planarity Testing/Embedding - 1.40.0}} and the extraction of multiple Kuratowski subdivisions is publicly available. Algorithms that locate a Kuratowski subgraph in linear time in vertices were developed by Williamson in the 1980s.{{citation
| last1 = Williamson | first1 = S. G.
| journal = Journal of the ACM
| pages = 681–693
| title = Depth First Search and Kuratowski Subgraphs
| volume = 31
| issue = 4
| year = 1984
| doi = 10.1145/1634.322451| s2cid = 8348222
| doi-access = free
}}
=Construction sequence method=
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).{{citation
| last1 = Schmidt | first1 = Jens M.
| contribution = The Mondshein Sequence
| volume = 8572
| doi = 10.1007/978-3-662-43948-7_80
| title = Automata, Languages, and Programming; Proceedings of the 41st International Colloquium on Automata, Languages and Programming (ICALP'14)
| pages = 967–978
| year = 2014| series = Lecture Notes in Computer Science
| isbn = 978-3-662-43947-0
}} The construction starts with K4 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.
===Dynamic algorithms===
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é,{{citation
| last1 = La Poutré | first1 = Johannes A.
| contribution = Alpha algorithms for incremental planarity testing
| title = Proceedings of the Twenty-Sixth Annual ACM Symposium on Theory of Computing (STOC)
| doi = 10.1145/195058.195439
| pages = 706–715
| year = 1994
| s2cid = 16799743
}} improving upon algorithms by Di Battista, Tamassia, and Westbrook.{{citation
| first1 = Giuseppe | last1 = Di Battista
| first2 = Roberto | last2 = Tamassia
| title = on-line maintenance of triconnected components with SPQR-trees
| journal = Algorithmica
| year = 1996
| volume = 15
| issue = 4
| pages = 302–318
| doi = 10.1007/BF01961541| s2cid = 7838334
| first1 = Roberto | last1 = Tamassia
| title = On-line planar graph embedding
| journal = Journal of Algorithms
| year = 1996
| volume = 21
| issue = 2
| pages = 201–239
| doi = 10.1006/jagm.1996.0044 }}{{citation
| first1 = Jeffery | last1 = Westbrook
| contribution = Fast Incremental Planarity Testing
| title = Automata, Languages and Programming, 19th International Colloquium, ICALP92
| year = 1992
| doi = 10.1007/3-540-55719-9_86
}} 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,{{citation
| first1 = Mihai | last1 = Pătrașcu | author1-link = Mihai Pătrașcu (computer scientist)
| first2 = Erik | last2 = Demaine | author2-link = Erik Demaine
| chapter = Lower Bounds for Dynamic Connectivity
| title = Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms
| year = 2004
| pages = 546–553 | doi = 10.1145/1007352.1007435
| isbn = 1581138520 | s2cid = 2121130 }} and a polylogarithmic update-time algorithm by Holm and Rotenberg,{{cite conference | last1 = Holm | first1 = Jacob | last2 = Rotenberg | first2 = Eva | editor1-last = Makarychev | editor1-first = Konstantin | editor2-last = Makarychev | editor2-first = Yury | editor3-last = Tulsiani | editor3-first = Madhur | editor4-last = Kamath | editor4-first = Gautam | editor5-last = Chuzhoy | editor5-first = Julia | editor5-link = Julia Chuzhoy | arxiv = 1911.03449 | contribution = Fully-dynamic planarity testing in polylogarithmic time | doi = 10.1145/3357713.3384249 | pages = 167–180 | publisher = Association for Computing Machinery | title = Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, Chicago, IL, USA, June 22-26, 2020 | year = 2020}} improving on sub-linear update-time algorithms by Eppstein, Galil, Italiano, Sarnak, and Spencer.{{citation
| first1 = David | last1 = Eppstein
| first2 = Zvi | last2 = Galil
| first3 = Giuseppe | last3 = Italiano
| first4 = Thomas | last4 = Spencer
| title = Separator based sparsification: I. planarity testing and minimum spanning trees
| year = 1996
| journal = Journal of Computer and System Sciences
| doi = 10.1006/jcss.1996.0002| doi-access = free
| first1 = Zvi | last1 = Galil
| first2 = Giuseppe | last2 = Italiano
| first3 = Neil | last3 = Sarnak
| title = Fully dynamic planarity testing with applications
| journal = Journal of the ACM
| year = 1999
| volume = 46
| pages = 28–91
| doi = 10.1145/300515.300517| s2cid = 7009330
| doi-access = free
}}