INPUT OUTPUT

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

Planar Graph Drawing by T. Nishizeki and S. Rahman | Graph Drawing: Algorithms for the Visualization of Graphs by Giuseppe Di Battista, Peter Eades, Roberto Tamassia, and Ionnis G. Tollis |

This page last modified on 2008-07-10 . www.algorist.com