Abstract:
W. T. Tutte published a paper in 1963 entitled "How to Draw a Graph".
Tutte's motivation was mathematical, and his paper can be seen as a contribution to
the long tradition of geometric representations of combinatorial objects.
Over the following 40-odd years, the motivation for creating visual representations
of graphs has changed from mathematical curiosity to visual analytics. Current
demand for graph drawing methods is now high, because of the potential for more
human-comprehensible visual forms in industries as diverse as biotechnology, homeland
security and sensor networks. Many new methods have been proposed, tested,
implemented, and found their way into commercial tools. This paper describes two
strands of this history: the force directed approach, and the planarity approach.
Both approaches originate in Tutte's paper.
Further, we demonstrate number of methods for graph visualization that can be derived
from the weighted version of Tutte's method. These include results on clustered planar
graphs, edge-disjoint paths, an animation method, interactions such as adding/deleting
vertices/edges and a focus-plus-context view method.