HOME

TheInfoList



OR:

In
graph theory In mathematics, graph theory is the study of ''graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conn ...
, the planarity testing problem is the
algorithm In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific problems or to perform a computation. Algorithms are used as specifications for performing ...
ic 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
algorithm In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific problems or to perform a computation. Algorithms are used as specifications for performing ...
s 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 In computer science, an algorithm is said to be asymptotically optimal if, roughly speaking, for large inputs it performs at worst a constant factor (independent of the input size) worse than the best possible algorithm. It is a term commonly e ...
. Rather than just being a single Boolean value, the output of a planarity testing algorithm may be a planar
graph embedding In topological graph theory, an embedding (also spelled imbedding) of a graph G on a surface \Sigma is a representation of G on \Sigma in which points of \Sigma are associated with vertices and simple arcs (homeomorphic images of ,1/math>) a ...
, 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 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 subd ...
that a graph is planar if and only if it does not contain a subgraph that is a subdivision of ''K''5 (the
complete graph In the mathematical field of graph theory, a complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge. A complete digraph is a directed graph in which every pair of distinct vertices is ...
on five vertices) or ''K''3,3 (the
utility graph As a topic of economics, utility is used to model worth or value. Its usage has evolved significantly over time. The term was introduced initially as a measure of pleasure or happiness as part of the theory of utilitarianism by moral philosoph ...
, a
complete bipartite graph In the mathematical field of graph theory, a complete bipartite graph or biclique is a special kind of bipartite graph where every vertex of the first set is connected to every vertex of the second set..Electronic edition page 17. Graph theory i ...
on six vertices, three of which connect to each of the other three). *
Wagner's theorem In graph theory, Wagner's theorem is a mathematical forbidden graph characterization of planar graphs, named after Klaus Wagner, stating that a finite graph is planar if and only if its minors include neither ''K''5 (the complete graph on five ...
that a graph is planar if and only if it does not contain a minor (subgraph of a contraction) that is isomorphic to ''K''5 or ''K''3,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 ''K''5 or ''K''3,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 space In graph theory, a branch of mathematics, the (binary) cycle space of an undirected graph is the set of its even-degree subgraphs. This set of subgraphs can be described algebraically as a vector space over the two-element finite field. The dime ...
s, *
Schnyder's theorem In graph theory, Schnyder's theorem is a characterization of planar graphs in terms of the order dimension of their incidence posets. It is named after Walter Schnyder, who published its proof in 1989. The incidence poset of an undirected graph ...
characterizing planar graphs by the
order dimension In mathematics, the dimension of a partially ordered set (poset) is the smallest number of total orders the intersection of which gives rise to the partial order. This concept is also sometimes called the order dimension or the Dushnik–Miller d ...
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 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. In 2012, Taylor 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 In the mathematical field of graph theory, an induced subgraph of a graph is another graph, formed from a subset of the vertices of the graph and ''all'' of the edges (from the original graph) connecting pairs of vertices in that subset. Definit ...
of the given graph, and adding vertices one at a time to this data structure. These methods began with an inefficient O(''n''2) method conceived by Lempel,
Even Even may refer to: General * Even (given name), a Norwegian male personal name * Even (surname) * Even (people), an ethnic group from Siberia and Russian Far East **Even language, a language spoken by the Evens * Odd and Even, a solitaire game wh ...
and Cederbaum in 1967. It was improved by Even and Tarjan, who found a linear-time solution for the ''s'',''t''-numbering step, and by
Booth Booth may refer to: People * Booth (surname) * Booth (given name) Fictional characters * August Wayne Booth, from the television series ''Once Upon A Time'' *Cliff Booth, a supporting character of the 2019 film ''Once Upon a Time in Hollywood ...
and Lueker, who developed the PQ tree data structure. With these improvements it is linear-time and outperforms the path addition method in practice., 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. In 1999, Shih and Hsu simplified these methods using the PC tree (an unrooted variant of the PQ tree) and a
postorder traversal In computer science, tree traversal (also known as tree search and walking the tree) is a form of graph traversal and refers to the process of visiting (e.g. retrieving, updating, or deleting) each node in a tree data structure, exactly once ...
of the depth-first search tree of the vertices.


Edge addition method

In 2004, John Boyer and Wendy Myrvold 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''5 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, de Mendez and Rosenstiehl.). See 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. The source code for the planarity test 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.


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). 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- Ackerman function update-time algorithm due to La Poutré, improving upon algorithms by Di Battista, Tamassia, and Westbrook. 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, and a polylogarithmic update-time algorithm by Holm and Rotenberg, improving on sub-linear update-time algorithms by Eppstein,
Galil The IMI Galil ( he, גליל) is a family of Israeli-made automatic rifles chambered for the 5.56×45mm NATO and 7.62×51mm NATO cartridges. Originally designed by Yisrael Galili and Yakov Lior in the late 1960s, the Galil was first produced ...
,
Italiano Italian (''italiano'' or ) is a Romance language of the Indo-European language family that evolved from the Vulgar Latin of the Roman Empire. Together with Sardinian, Italian is the least divergent language from Latin. Spoken by about 85 ...
, Sarnak, and Spencer{{citation , first1 = Zvi , last1 = Galil , first2 = Giuseppe , last2 = Italiano , first3 = Neil , last3 = Sarnak , contribution = Fully dynamic planarity testing with applications , title = Journal of the ACM , year = 1999 , doi = 10.1145/300515.300517.


References

{{reflist, colwidth=30em Planar graphs Computational problems in graph theory