A graph may he drawn in many different ways. We investigate how to draw a graph nicely, in the sense of being visually pleasing. We discuss the history of this field, and look at several algorithms for drawing graphs.
For planar graphs this problem has been algorithmically solved: that is, there is an algorithm which takes a n vertex planar graph and places the vertices at some of the nodes of an n-2 by 2n-4 array so that each edge of the planar graph can be drawn with a straight line. We describe in detail one particular implementation of this algorithm, give some examples in which this embedding is pleasing, and give a number of examples in which this grid embedding is not as visually pleasing another drawing of the same graph.
For the more difficult problem of drawing a nonplanar graph, we investigate a spring based algorithm. We give a number of examples in which
this heuristic produces more pleasing drawings than those produced by the planar embedding and a few cases where it fails to do so. / Graduation date: 1997
| Identifer | oai:union.ndltd.org:ORGSU/oai:ir.library.oregonstate.edu:1957/34200 |
| Date | 24 April 1995 |
| Creators | Palmer, Paul A. |
| Contributors | Cull, Paul |
| Source Sets | Oregon State University |
| Language | en_US |
| Detected Language | English |
| Type | Thesis/Dissertation |
Page generated in 0.0021 seconds