Drawing
Home ] Up ] Trees ] Planar ] Non-planar ] Interactive ]

Trees
Planar
Non-planar
Interactive

The field of graph drawing studies how graphs and networks can be drawn to provide a more understandable visual representation of the graph [Di Battista, Eades, Tamassia and Tollis, 1994], [Becker, et al., 1991], [Eick, 1996], [Cruz and Tamassia, 1994]. [Di Battista, Eades, Tamassia and Tollis, 1994] and [Mutzel, et al., 1998] maintain thorough annotated bibliographies of graph drawing. A "more understandable visual representation" depends on at least the following two factors:

  1. The topology of the graph to be drawn, including:
    Tree
    Planar
    Non-planar
  2. The criteria used to measure the quality of the visual layout, including:
minimum number of edges that cross
minimum area
minimum number of bent edges
preserve symmetry

In addition to these automatic layout techniques, interactive techniques including constraint-based techniques and fish-eye views have been successfully applied to the graph layout problem.  Algorithms to draw graphs are available from several sources including [Skiena, 1990], [Tom Sawyer Software, 1995].

Drawing a dense graph, a graph having many edges relative to the number of nodes, as a set of icons interconnected by lines may be a losing proposition.  The large number of edges will create a tangle of spaghetti that may be too difficult to comprehend no matter how much effort is spent on the drawing.  Dense graphs may be best "drawn" as a adjacency matrix, which will contain no crossing edges.   It is unknown if any experiements have been conducted to explore the density level at which a matrix representation is more readily understood (the author thanks Bob Fourer for this insight).

Contact the author. Contact the editor of ITORMS
Search by keyword. Navigation Hints
Table of contents. References
Read or make public comments about the site.

Return to home page.

Last updated 09/25/98

itormsnw.gif (13174 bytes)