The Algorithm Design Manual
About the Book
Programming Challenges

The Stony Brook Algorithm Repository

Steven Skiena
Stony Brook University
Dept. of Computer Science

1.4.12 Planarity Detection and Embedding

Problem Input | Problem Output

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.


Implementations

  • LEDA - A Library of Efficient Data Types and Algorithms (C++) (rating 10)
  • JGraphEd: Java Graph Editing application (Java) (rating 9)
  • GOBLIN: A Graph Object Library for Network (C++) (rating 9)
  • GRASP- Greedy randomized adaptive search program (FORTRAN) (rating 8)
  • GraphEd -- Graph Editor and Layout Program (C) (rating 7)
  • Combinatorica (Mathematica) (rating 2)

  • Recommended Books

    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

    Related Problems


      
    Drawing Graphs Nicely
      
    Drawing Trees
      
    Graph Partition



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