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.10 Drawing Graphs Nicely

Problem Input | Problem Output

INPUT                    OUTPUT


Input Description: A graph G.

Problem: Give a drawing of graph G which accurately reflects its structure.

Excerpt from The Algorithm Design Manual: Drawing graphs nicely is a problem that constantly arises in applications, such as displaying file directory trees or circuit schematic diagrams.Yet it is inherently ill-defined. What exactly does nicely mean? We seek an algorithm that shows off the structure of the graph so the viewer can best understand it. We also seek a drawing that looks aesthetically pleasing. Unfortunately, these are ``soft'' criteria for which it is impossible to design an optimization algorithm. Indeed, it is possible to come up with two or more radically different drawings of certain graphs and have each be most appropriate in certain contexts.

Several ``hard'' criteria can partially measure the quality of a drawing:

Unfortunately, these goals are mutually contradictory, and the problem of finding the best drawing under any nonempty subset of them will likely be NP-complete.


Implementations

  • Graphviz - Graph Visualization Software (C) (rating 9)
  • JGraphT: Java graph library (Java) (rating 9)
  • Tom Sawyer Software (Binary) (rating 8)
  • yWorks - The Diagramming Company (Binary) (rating 8)
  • ILOG JViews Visualization Products (Binary) (rating 8)
  • Networks / Pajek: Program for Large Network Analysis (Binary) (rating 8)

  • Recommended Books

    Handbook of Graph Drawing and Visualization by R. Tamassia Exploratory Social Network Analysis with Pajek by W. Nooy and A. Mrvar and V. Batagelj Drawing Graphs: Methods and Models by M. Kaufmann and D. Wagner
    Graph Drawing: Algorithms for the Visualization of Graphs by Giuseppe Di Battista, Peter Eades, Roberto Tamassia, and Ionnis G. Tollis Computational Discrete Mathematics: Combinatorics and Graph Theory with Mathematica by S. Pemmaraju and S. Skiena

    Related Problems


      
    Drawing Trees
      
    Planarity Detection and Embedding



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