Input description: A graph G.
Problem description: Can G be drawn in the plane such that no two edges cross? If so, produce such a drawing.
Discussion: 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), 
,
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.
The study of planarity has motivated much of the development of
graph theory.
To get a better appreciation of the subtleties of planar drawings,
the reader is urged to construct a planar (noncrossing)
embedding for the graph 
,
the complete graph on five vertices with any single edge deleted.
Then construct such an embedding where all the edges are straight.
Finally, attempt to do the same for 
itself.
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.
Algorithms for planarity testing begin by embedding an arbitrary cycle from the graph in the plane and then considering additional paths in G between vertices on this cycle. Whenever two such paths cross, one must be drawn outside the cycle and one inside. When three such paths mutually cross, there is no way to resolve the problem, and so the graph cannot be planar. Linear-time algorithms for planarity detection are based on depth-first search, but they are subtle and complicated enough that you would be wise to use an existing implementation if you can.
Such path-crossing algorithms can be used to construct a planar embedding
by inserting the paths into the drawing one by one.
Unfortunately, because they work in an incremental manner,
nothing prevents them from inserting many vertices and
edges into a relatively small area of the drawing.
Such cramping makes the drawing ugly and hard to understand, and is
a major problem with planar-embedding algorithms.
More recently, algorithms have been devised
that construct planar-grid embeddings, where
each vertex lies on a 
grid.
Thus no region can get too cramped and no edge can get too long.
Still, the resulting drawings tend not to look as natural
as one might hope.
For nonplanar graphs, what is often sought is a drawing that minimizes the number of crossings. Unfortunately, computing the crossing number is NP-complete. A useful heuristic extracts a large planar subgraph of G, embeds this subgraph, and then inserts the remaining edges one by one so as to minimize the number of crossings. This won't do much for dense graphs, which are doomed to have a large number of crossings, but it will work well for graphs that are almost planar, such as road networks with overpasses or printed circuit boards with multiple layers. Large planar subgraphs can be found by modifying planarity-testing algorithms to delete troublemaking edges.
Implementations: LEDA (see Section 
) provides a nice set of data structures
and algorithms to support working on planar subdivisions.
Included are both linear-time planarity testing and constructing straight-line
planar-grid embeddings.
GraphEd
includes
an implementation of both planarity testing and planar graph layout.
See Section for more details on GraphEd.
Combinatorica [Ski90] provides a (slow) Mathematica implementation
of planarity testing.
See Section .
Notes: Kuratowski [Kur30]
gave the first characterization of planar graphs, namely that
they do not contain a subgraph homeomorphic to 
or .
Thus if you are still working on the exercise to embed ,
now is an appropriate time to give it up.
Fary's theorem [F48]
states that every planar graph can be drawn such that each
edge is straight.
Hopcroft and Tarjan [HT74]
gave the first linear-time algorithm for drawing graphs.
Expositions on linear-time planarity testing include [Eve79a].
Nishizeki and Chiba [NC88]
provide a good reference to the algorithmic theory
of planar graphs.
Efficient algorithms for planar grid embeddings were first developed
by [dFPP88].
See [CHT90] for an algorithm to find the maximum planar subgraph
of a nonplanar graph.
Outerplanar graphs are those that can be drawn such that all vertices
lie on the outer face of the drawing.
Such graphs can be characterized as having no subgraph homeomorphic
to 
and can be recognized and embedded in linear time.
Related Problems: Graph partition (see page ),
drawing trees (see page ).
