1.4.12 Planarity Detection and Embedding
INPUT OUTPUT
Input Description:
A graph G.
Problem:
Can G be drawn in the plane such that no two edges cross?
If so, produce such a drawing.
Excerpt from
The Algorithm Design Manual:
Planar drawings (or embeddings) make it easy to understand the structure of a given graph by eliminating
crossing edges, which are often confused as additional vertices. Graphs arising in many applications, such as road
networks or printed circuit boards, are naturally planar because they are defined by surface structures.
Planar graphs have a variety of nice properties, which can be exploited to yield faster algorithms for many
problems on planar graphs. Perhaps the most important property is that every planar graph is sparse.
Euler's formula shows that for planar graph G=(V,E), |E| \leq 3 |V| - 6, so every planar graph
contains a linear number of edges, and further, every planar graph must contain a vertex of degree at most
5. Since every subgraph of a planar graph is planar, this means that there is always a sequence of
low-degree vertices whose deletion from G eventually leaves the empty graph.
It is useful to distinguish the problem of planarity testing (does a graph have a planar drawing) from constructing
planar embeddings (actually finding the drawing), although both can be done in linear time. Surprisingly, many
efficient algorithms for planar graphs do not make use of the drawing but use the low-degree deletion sequence
described above.
Recommended Books
Related Problems
This page last modified on 2008-07-10
.
www.algorist.com
Planar Graph Drawing
Graph Drawing: Algorithms for the Visualization of Graphs
