Planarity testing
Encyclopedia
In graph theory
, the planarity testing problem asks whether, given a graph, that graph is a planar graph
(can be drawn in the plane without edge intersections). This is a well-studied problem in computer science
for which many practical algorithm
s have emerged, many taking advantage of novel data structure
s. 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
.
we can assume the edges in the graph drawing
, if any, are straight line segments. Given such a drawing for the graph, we can verify that there are no crossings using well-known line segment intersection
algorithms that operate in O(n log n) time. However, this is not a particularly good solution, for several reasons:
For these reasons, planarity testing algorithms take advantage of theorems in graph theory that characterize the set of planar graphs in terms that are independent of graph drawings. One of these is Kuratowski's theorem, which states that:
A graph can be demonstrated to be nonplanar by exhibiting a subgraph matching the above description, and this can be easily verified, which places the problem in co-NP. However, this also doesn't by itself produce a good algorithm, since there are a large number of subgraphs to consider (K5 and K3,3 are fixed in size, but a graph can contain 2Ω(m) subdivisions of them).
A simple theorem allows graphs with too many edges to be quickly determined to be nonplanar, but cannot be used to establish planarity. If v is the number of vertices (at least 3) and e is the number of edges, then the following imply nonplanarity:
For this reason n can be taken to be either the number of vertices or edges when using big O notation with planar graphs, since they differ by at most a constant multiple.
and Tarjan
was the first published linear-time planarity testing algorithm in 1974.
, Even
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 and Lueker, who developed the PQ tree
data structure. With these improvements it is linear-time and outperforms the path addition method in practice. This method was also extended to allow a planar embedding (drawing) to be efficiently computed for a planar graph.
tree of the vertices.
Graph theory
In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of...
, the planarity testing problem asks whether, given a graph, that graph is a planar graph
Planar graph
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...
(can be drawn in the plane without edge intersections). This is a well-studied problem in computer science
Computer science
Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...
for which many practical algorithm
Algorithm
In mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning...
s have emerged, many taking advantage of novel data structure
Data structure
In computer science, a data structure is a particular way of storing and organizing data in a computer so that it can be used efficiently.Different kinds of data structures are suited to different kinds of applications, and some are highly specialized to specific tasks...
s. Most of these methods operate in O
Big O notation
In mathematics, big O notation is used to describe the limiting behavior of a function when the argument tends towards a particular value or infinity, usually in terms of simpler functions. It is a member of a larger family of notations that is called Landau notation, Bachmann-Landau notation, or...
(n) time (linear time), where n is the number of edges (or vertices) in the graph, which is asymptotically optimal
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 worse than the best possible algorithm...
.
Simple algorithms and planarity characterizations
By Fáry's theoremFáry's theorem
In mathematics, 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...
we can assume the edges in the graph drawing
Graph drawing
Graph drawing is an area of mathematics and computer science combining methods from geometric graph theory and information visualization to derive two-dimensional depictions of graphs arising from applications such as social network analysis, cartography, and bioinformatics...
, if any, are straight line segments. Given such a drawing for the graph, we can verify that there are no crossings using well-known line segment intersection
Line segment intersection
In computational geometry, the line segment intersection problem supplies a list of line segments in the plane and asks us to determine whether any two of them intersect, or cross....
algorithms that operate in O(n log n) time. However, this is not a particularly good solution, for several reasons:
- There's no obvious way to find a drawing, a problem which is considerably more difficult than planarity testing;
- Line segment intersection algorithms are more expensive than good planarity testing algorithms;
- It does not extend to verifying nonplanarity, since there is no obvious way of enumerating all possible drawings.
For these reasons, planarity testing algorithms take advantage of theorems in graph theory that characterize the set of planar graphs in terms that are independent of graph drawings. One of these is Kuratowski's theorem, which states that:
- A finite graph is planar if and only ifIf and only ifIn logic and related fields such as mathematics and philosophy, if and only if is a biconditional logical connective between statements....
it does not contain a subgraph that is a subdivision of K5 (the complete graphComplete graphIn 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.-Properties:...
on five verticesVertex (graph theory)In graph theory, a vertex or node is the fundamental unit out of which graphs are formed: an undirected graph consists of a set of vertices and a set of edges , while a directed graph consists of a set of vertices and a set of arcs...
) or K3,3 (complete bipartite graphComplete bipartite graphIn 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.- Definition :...
on six vertices, three of which connect to each of the other three).
A graph can be demonstrated to be nonplanar by exhibiting a subgraph matching the above description, and this can be easily verified, which places the problem in co-NP. However, this also doesn't by itself produce a good algorithm, since there are a large number of subgraphs to consider (K5 and K3,3 are fixed in size, but a graph can contain 2Ω(m) subdivisions of them).
A simple theorem allows graphs with too many edges to be quickly determined to be nonplanar, but cannot be used to establish planarity. If v is the number of vertices (at least 3) and e is the number of edges, then the following imply nonplanarity:
- e > 3v − 6 or;
- There are no cycles of length 3 and e > 2v − 4.
For this reason n can be taken to be either the number of vertices or edges when using big O notation with planar graphs, since they differ by at most a constant multiple.
Path addition method
The classic path addition method of HopcroftJohn Hopcroft
John Edward Hopcroft is an American theoretical computer scientist. His textbooks on theory of computation and data structures are regarded as standards in their fields. He is the IBM Professor of Engineering and Applied Mathematics in Computer Science at Cornell University.He received his...
and Tarjan
Robert Tarjan
Robert Endre Tarjan is a renowned American computer scientist. He is the discoverer of several important graph algorithms, including Tarjan's off-line least common ancestors algorithm, and co-inventor of both splay trees and Fibonacci heaps. Tarjan is currently the James S...
was the first published linear-time planarity testing algorithm in 1974.
PQ tree vertex addition method
The vertex addition method began with an inefficient O(n2) method conceived by LempelAbraham Lempel
Abraham Lempel is an Israeli computer scientist and one of the fathers of the LZ family of lossless data compression algorithms.Lempel was born on 10 February 1936 in Lwów, Poland . He studied at Technion - Israel Institute of Technology, and received a B.Sc. in 1963, M.Sc. in 1965, and D.Sc. in...
, Even
Shimon Even
Shimon Even was an Israeli computer science researcher. His main topics of interest included algorithms, graph theory and cryptography. He was a member of the Computer Science Department at the Technion since 1974...
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 and Lueker, who developed the PQ tree
PQ tree
A PQ tree is a tree-based data structure that represents a family of permutations on a set of elements, discovered and named by Kellogg S. Booth and George S. Lueker in 1976. It is a rooted, labeled tree, in which each element is represented by one of the leaf nodes, and each non-leaf node is...
data structure. With these improvements it is linear-time and outperforms the path addition method in practice. This method was also extended to allow a planar embedding (drawing) to be efficiently computed for a planar graph.
PC tree vertex addition method
In 1999, Shih and Hsu developed a planarity testing algorithm that was significantly simpler than classical methods based on a new type of data structure called the PC tree and a postorder traversal of the depth-first searchDepth-first search
Depth-first search is an algorithm for traversing or searching a tree, tree structure, or graph. One starts at the root and explores as far as possible along each branch before backtracking....
tree of the vertices.