Planarity testing

Last updated

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.

Contents

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:

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. 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 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. [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]

Edge addition method

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 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 [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]

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). [19] 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é, [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]

Related Research Articles

In graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints. In other words, it can be drawn in such a way that no edges cross each other. Such a drawing is called a plane graph or planar embedding of the graph. A plane graph can be defined as a planar graph with a mapping from every node to a point on a plane, and from every edge to a plane curve on that plane, such that the extreme points of each curve are the points mapped from its end nodes, and all curves are disjoint except on their extreme points.

<span class="mw-page-title-main">Robert Tarjan</span> American computer scientist and mathematician

Robert Endre Tarjan is an American computer scientist and mathematician. He is the discoverer of several graph theory algorithms, including his strongly connected components algorithm, and co-inventor of both splay trees and Fibonacci heaps. Tarjan is currently the James S. McDonnell Distinguished University Professor of Computer Science at Princeton University.

<span class="mw-page-title-main">Kuratowski's theorem</span> On forbidden subgraphs in planar graphs

In graph theory, Kuratowski's theorem is a mathematical forbidden graph characterization of planar graphs, named after Kazimierz Kuratowski. It states that a finite graph is planar if and only if it does not contain a subgraph that is a subdivision of or of .

In graph theory, an undirected graph H is called a minor of the graph G if H can be formed from G by deleting edges, vertices and by contracting edges.

<span class="mw-page-title-main">Strongly connected component</span> Partition of a graph whose components are reachable from all vertices

In the mathematical theory of directed graphs, a graph is said to be strongly connected if every vertex is reachable from every other vertex. The strongly connected components of an arbitrary directed graph form a partition into subgraphs that are themselves strongly connected. It is possible to test the strong connectivity of a graph, or to find its strongly connected components, in linear time (that is, Θ(V + E)).

<span class="mw-page-title-main">Level structure</span>

In the mathematical subfield of graph theory a level structure of an undirected graph is a partition of the vertices into subsets that have the same distance from a given root vertex.

<span class="mw-page-title-main">Topological graph theory</span> Branch of the mathematical field of graph theory

In mathematics, topological graph theory is a branch of graph theory. It studies the embedding of graphs in surfaces, spatial embeddings of graphs, and graphs as topological spaces. It also studies immersions of graphs.

<span class="mw-page-title-main">Biconnected component</span> Maximal biconnected subgraph

In graph theory, a biconnected component is a maximal biconnected subgraph. Any connected graph decomposes into a tree of biconnected components called the block-cut tree of the graph. The blocks are attached to each other at shared vertices called cut vertices or separating vertices or articulation points. Specifically, a cut vertex is any vertex whose removal increases the number of connected components.

In the mathematical field of graph theory, Fáry's theorem states that any simple, planar graph can be drawn without crossings so that its edges are straight line segments. That is, the ability to draw graph edges as curves instead of as straight line segments does not allow a larger class of graphs to be drawn. The theorem is named after István Fáry, although it was proved independently by Klaus Wagner (1936), Fáry (1948), and Sherman K. Stein (1951).

<span class="mw-page-title-main">Graph embedding</span> Embedding a graph in a topological space, often Euclidean

In topological graph theory, an embedding of a graph on a surface is a representation of on in which points of are associated with vertices and simple arcs are associated with edges in such a way that:

<span class="mw-page-title-main">SPQR tree</span> Representation of a graphs triconnected components

In graph theory, a branch of mathematics, the triconnected components of a biconnected graph are a system of smaller graphs that describe all of the 2-vertex cuts in the graph. An SPQR tree is a tree data structure used in computer science, and more specifically graph algorithms, to represent the triconnected components of a graph. The SPQR tree of a graph may be constructed in linear time and has several applications in dynamic graph algorithms and graph drawing.

A program structure tree (PST) is a hierarchical diagram that displays the nesting relationship of single-entry single-exit (SESE) fragments/regions, showing the organization of a computer program. Nodes in this tree represent SESE regions of the program, while edges represent nesting regions. The PST is defined for all control flow graphs.

Planarity is a 2005 puzzle computer game by John Tantalo, based on a concept by Mary Radcliffe at Western Michigan University. The name comes from the concept of planar graphs in graph theory; these are graphs that can be embedded in the Euclidean plane so that no edges intersect. By Fáry's theorem, if a graph is planar, it can be drawn without crossings so that all of its edges are straight line segments. In the planarity game, the player is presented with a circular layout of a planar graph, with all the vertices placed on a single circle and with many crossings. The goal for the player is to eliminate all of the crossings and construct a straight-line embedding of the graph by moving the vertices one by one into better positions.

In graph theory, a branch of mathematics, many important families of graphs can be described by a finite set of individual graphs that do not belong to the family and further exclude all graphs from the family which contain any of these forbidden graphs as (induced) subgraph or minor.

In graph theory, the planar separator theorem is a form of isoperimetric inequality for planar graphs, that states that any planar graph can be split into smaller pieces by removing a small number of vertices. Specifically, the removal of vertices from an n-vertex graph can partition the graph into disjoint subgraphs each of which has at most vertices.

<span class="mw-page-title-main">Cycle basis</span> Cycles in a graph that generate all cycles

In graph theory, a branch of mathematics, a cycle basis of an undirected graph is a set of simple cycles that forms a basis of the cycle space of the graph. That is, it is a minimal set of cycles that allows every even-degree subgraph to be expressed as a symmetric difference of basis cycles.

<span class="mw-page-title-main">Apex graph</span> Graph which can be made planar by removing a single node

In graph theory, a branch of mathematics, an apex graph is a graph that can be made planar by the removal of a single vertex. The deleted vertex is called an apex of the graph. It is an apex, not the apex because an apex graph may have more than one apex; for example, in the minimal nonplanar graphs K5 or K3,3, every vertex is an apex. The apex graphs include graphs that are themselves planar, in which case again every vertex is an apex. The null graph is also counted as an apex graph even though it has no vertex to remove.

In graph drawing, a universal point set of order n is a set S of points in the Euclidean plane with the property that every n-vertex planar graph has a straight-line drawing in which the vertices are all placed at points of S.

In graph theory, a bipolar orientation or st-orientation of an undirected graph is an assignment of a direction to each edge that causes the graph to become a directed acyclic graph with a single source s and a single sink t, and an st-numbering of the graph is a topological ordering of the resulting directed acyclic graph.

In the mathematical field of graph theory, planarization is a method of extending graph drawing methods from planar graphs to graphs that are not planar, by embedding the non-planar graphs within a larger planar graph.

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, hdl: 1813/6011 , S2CID   6279825 .
  2. ↑ Mehlhorn, Kurt; Mutzel, Petra (1996), "On the Embedding Phase of the Hopcroft and Tarjan Planarity Testing Algorithm" (PDF), Algorithmica, 16 (2): 233–242, doi:10.1007/bf01940648, hdl: 11858/00-001M-0000-0014-B51D-B , S2CID   10014462
  3. ↑ Mehlhorn, Kurt; Mutzel, Petra; Näher, Stefan (1993), An Implementation of the Hopcroft and Tarjan Planarity Test and Embedding Algorithm
  4. ↑ Mehlhorn, Kurt; Näher, Stefan (1995), "LEDA: A library of efficient data types and algorithms", Communications of the ACM, 38 (1): 96–102, CiteSeerX   10.1.1.54.9556 , doi:10.1145/204865.204889, S2CID   2560175
  5. ↑ Taylor, Martyn G. (2012). Planarity Testing by Path Addition (Ph.D.). University of Kent. Archived from the original on 2016-03-05. Alt URL
  6. ↑ 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.
  7. ↑ 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 .
  8. ↑ Boyer & Myrvold (2004), p. 243: “Its implementation in LEDA is slower than LEDA implementations of many other O(n)-time planarity algorithms.”
  9. ↑ Chiba, N.; Nishizeki, T.; Abe, A.; Ozawa, T. (1985), "A linear algorithm for embedding planar graphs using PQ–trees", Journal of Computer and System Sciences, 30 (1): 54–76, doi: 10.1016/0022-0000(85)90004-2 .
  10. ↑ 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 .
  11. ↑ 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, doi: 10.7155/jgaa.00091 .
  12. ↑ 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, arXiv: math/0610935 , Bibcode:2006math.....10935D, doi:10.1142/S0129054106004248, S2CID   40107560 .
  13. ↑ Brandes, Ulrik (2009), The left-right planarity test (PDF).
  14. ↑ 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
  15. ↑ 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. doi:10.1007/978-3-540-77537-9_17. ISBN   978-3-540-77536-2..
  16. 1 2 "OGDF - Open Graph Drawing Framework: Start".
  17. ↑ "Boost Graph Library: Boyer-Myrvold Planarity Testing/Embedding - 1.40.0".
  18. ↑ Williamson, S. G. (1984), "Depth First Search and Kuratowski Subgraphs", Journal of the ACM, 31 (4): 681–693, doi: 10.1145/1634.322451 , S2CID   8348222
  19. ↑ Schmidt, Jens M. (2014), "The Mondshein Sequence", Automata, Languages, and Programming; Proceedings of the 41st International Colloquium on Automata, Languages and Programming (ICALP'14), Lecture Notes in Computer Science, vol. 8572, pp. 967–978, doi:10.1007/978-3-662-43948-7_80, ISBN   978-3-662-43947-0
  20. ↑ La Poutré, Johannes A. (1994), "Alpha algorithms for incremental planarity testing", Proceedings of the Twenty-Sixth Annual ACM Symposium on Theory of Computing (STOC), pp. 706–715, doi:10.1145/195058.195439, S2CID   16799743
  21. ↑ Di Battista, Giuseppe; Tamassia, Roberto (1996), "on-line maintenance of triconnected components with SPQR-trees", Algorithmica, 15 (4): 302–318, doi:10.1007/BF01961541, S2CID   7838334
  22. ↑ Tamassia, Roberto (1996), "On-line planar graph embedding", Journal of Algorithms, 21 (2): 201–239, doi:10.1006/jagm.1996.0044
  23. ↑ Westbrook, Jeffery (1992), "Fast Incremental Planarity Testing", Automata, Languages and Programming, 19th International Colloquium, ICALP92, doi:10.1007/3-540-55719-9_86
  24. ↑ Pătrașcu, Mihai; Demaine, Erik (2004), "Lower Bounds for Dynamic Connectivity", Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 546–553, doi:10.1145/1007352.1007435, ISBN   1581138520, S2CID   2121130
  25. ↑ Holm, Jacob; Rotenberg, Eva (2020). "Fully-dynamic planarity testing in polylogarithmic time". In Makarychev, Konstantin; Makarychev, Yury; Tulsiani, Madhur; Kamath, Gautam; Chuzhoy, Julia (eds.). Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, Chicago, IL, USA, June 22-26, 2020. Association for Computing Machinery. pp. 167–180. arXiv: 1911.03449 . doi:10.1145/3357713.3384249.
  26. ↑ Eppstein, David; Galil, Zvi; Italiano, Giuseppe; Spencer, Thomas (1996), "Separator based sparsification: I. planarity testing and minimum spanning trees", Journal of Computer and System Sciences, doi: 10.1006/jcss.1996.0002
  27. ↑ Galil, Zvi; Italiano, Giuseppe; Sarnak, Neil (1999), "Fully dynamic planarity testing with applications", Journal of the ACM, 46: 28–91, doi: 10.1145/300515.300517 , S2CID   7009330
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.