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.

Implementations

  • GraphEd -- Graph Editor and Layout Program (C) (rating 8)
  • LEDA - A Library of Efficient Data Types and Algorithms (C++) (rating 7)
  • Combinatorica (Mathematica) (rating 2)

    Related Problems

  • Drawing Graphs Nicely
  • Drawing Trees
  • Graph Partition

    Go to the corresponding chapter in the book
    About the Book
    Send us Mail
    Go to Main Page

    This page last modified on Tue Jun 03, 1997 .