Drawing graphs nicely Public Deposited

http://ir.library.oregonstate.edu/concern/graduate_thesis_or_dissertations/41687m723

Descriptions

Attribute NameValues
Creator
Abstract or Summary
  • 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.
Resource Type
Date Available
Date Copyright
Date Issued
Degree Level
Degree Name
Degree Field
Degree Grantor
Commencement Year
Advisor
Academic Affiliation
Non-Academic Affiliation
Subject
Rights Statement
Peer Reviewed
Language
Digitization Specifications
  • File scanned at 300 ppi (Monochrome, 8-bit Grayscale) using ScandAll PRO 1.8.1 on a Fi-6670 in PDF format. CVista PdfCompressor 4.0 was used for pdf compression and textual OCR.
Replaces
Additional Information
  • description.provenance : Approved for entry into archive by Patricia Black(patricia.black@oregonstate.edu) on 2012-10-08T17:22:50Z (GMT) No. of bitstreams: 1 PalmerPaulA1997.pdf: 2393724 bytes, checksum: 3d7623f9ed1511bd86d5b69bdef8021f (MD5)
  • description.provenance : Submitted by John Valentino (valentjo@onid.orst.edu) on 2012-10-05T23:41:35Z No. of bitstreams: 1 PalmerPaulA1997.pdf: 2393724 bytes, checksum: 3d7623f9ed1511bd86d5b69bdef8021f (MD5)
  • description.provenance : Made available in DSpace on 2012-10-08T17:24:32Z (GMT). No. of bitstreams: 1 PalmerPaulA1997.pdf: 2393724 bytes, checksum: 3d7623f9ed1511bd86d5b69bdef8021f (MD5) Previous issue date: 1995-04-24
  • description.provenance : Approved for entry into archive by Patricia Black(patricia.black@oregonstate.edu) on 2012-10-08T17:24:32Z (GMT) No. of bitstreams: 1 PalmerPaulA1997.pdf: 2393724 bytes, checksum: 3d7623f9ed1511bd86d5b69bdef8021f (MD5)

Relationships

Parents:

This work has no parents.

Last modified

Downloadable Content

Download PDF

Items