Planarity testing


Planarity testing

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

Simple algorithms and planarity characterizations

By Fáry's theorem 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:

* 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 if it does not contain a subgraph that is a subdivision of "K"5 (the complete graph on five vertices) or "K"3,3 (complete bipartite graph 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 ("K"5 and "K"3,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" > 3"v" − 6 "or";: There are no cycles of length 3 and "e" > 2"v" − 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 Hopcroft and Tarjan [J. Hopcroft and R. Tarjan. Efficient planarity testing. Journal of the Association for Computing Machinery, vol.21, no.4, pp.549–568. 1974.] 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("n"2) method conceived by Lempel, Even and Cederbaum in 1967. [A. Lempel, S. Even, and I. Cederbaum. An algorithm for planarity testing of graphs. In P. Rosenstiehl, editor, Theory of Graphs, pages 215–232, New York, 1967. Gordon and Breach.] It was improved by Even and Tarjan, who found a linear-time solution for the "s","t"-numbering step, [S. Even and R. E. Tarjan. Computing an st-numbering. Theoretical Computer Science, 2: pp.339–344. 1976.] and by Booth and Lueker, who developed the PQ tree data structure. With these improvements it is linear-time and outcompetes the path addition method in practice. [Boyer and Myrvold, pg.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. [N. Chiba, T. Nishizeki, A. Abe, and T. Ozawa. A linear algorithm for embedding planar graphs using PQ–trees. Journal of Computer and Systems Sciences, 30:pp.54–76. 1985.]

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 search tree of the vertices. [W. K. Shih and W. L. Hsu. A new planarity test. Theoretical Computer Science, 223:pp.179–191. 1999.]

Edge addition method

In 2004, Boyer and Myrvold [John M. Boyer and Wendy J. Myrvold. Simplified Planarity. Journal of Graph Algorithms and Applications, vol.8, no.3, pp.241–273. 2004.] 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 Frayseeix, de Mendez and Rosenstiehl [H. de Fraysseix, P. O. de Mendez, P. Rosenstiehl. Trémaux Trees and Planarity. Int. J. Found. Comput. Sci., 2006, 17, 1017-1030] ). See [J. M. Boyer, P. F. Cortese, M. Patrignani, G. D. Battista. Stop Minding Your P's and Q's: Implementing a Fast and Simple DFS-Based Planarity Testing and Embedding Algorithm. Proc. GD '03, Springer-Verlag, 2003, 2912, 25-36] 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 [M. Chimani, P. Mutzel, J. M. Schmidt. Efficient Extraction of Multiple Kuratowski Subdivisions. 15th International Symposium on Graph Drawing (GD'07), Sydney, Australia, 2008, 159-170] . The source code for the planarity test and the extraction of multiple Kuratowski subdivisions is publicly available [http://www.ogdf.net] .

References


Wikimedia Foundation. 2010.

Look at other dictionaries:

  • Non-contact wafer testing — Wafer testing is a normal step in semiconductor device fabrication, used to detect defects in integrated circuits (IC) before they are assembled during the IC packaging step. Traditional (contact) wafer testing Probing ICs while they are still on …   Wikipedia

  • Planar graph — Example graphs Planar Nonplanar Butterfly graph K5 The complete graph K4 …   Wikipedia

  • 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… …   Wikipedia

  • Topological graph theory — In mathematics topological graph theory is a branch of graph theory. It studies the embedding of graphs in surfaces, and graphs as topological spaces. [J.L. Gross and T.W. Tucker, Topological graph theory, Wiley Interscience, 1987] Embedding a… …   Wikipedia

  • Depth-first search — Order in which the nodes are visited Class Search algorithm Data structure Graph Worst case performance …   Wikipedia

  • Théorème de Robertson-Seymour — En mathématiques, et plus précisément en théorie des graphes, le théorème de Robertson–Seymour (parfois également appelé le théorème des mineurs, et connu, avant qu il soit démontré, sous le nom de conjecture de Wagner), est un théorème démontré… …   Wikipédia en Français

  • Pierre Rosenstiehl — (born in 1933) is a French mathematician at the École des Hautes Études en Sciences Sociales (Paris). He is particularly active in graph theory and recognized for his work on planar graphs and graph drawing. The Fraysseix Rosenstiehl s planarity… …   Wikipedia

  • Robert Tarjan — Infobox Scientist name = Robert Endre Tarjan image width = caption = birth date = Birth date and age|1948|4|30|mf=y birth place = Pomona, California death date = death place = residence = citizenship = nationality = ethnicity = field = Computer… …   Wikipedia

  • SPQR-tree — The SPQR tree is a tree data structure that represents the decomposition of a biconnected graph with respect to its triconnected components.It was introduced by Di Battista and Tamassia [cite journal author = Di Battista, G. and Tamassia, R. year …   Wikipedia

  • List of mathematics articles (P) — NOTOC P P = NP problem P adic analysis P adic number P adic order P compact group P group P² irreducible P Laplacian P matrix P rep P value P vector P y method Pacific Journal of Mathematics Package merge algorithm Packed storage matrix Packing… …   Wikipedia