Persistent Link:
http://hdl.handle.net/10150/195738
Title:
Simultaneous Embedding and Level Planarity
Author:
Estrella Balderrama, Alejandro
Issue Date:
2009
Publisher:
The University of Arizona.
Rights:
Copyright © is held by the author. Digital access to this material is made possible by the University Libraries, University of Arizona. Further transmission, reproduction or presentation (such as public display or performance) of protected items is prohibited except with permission of the author.
Abstract:
Graphs are a common model for representing information consisting of a set of objects or entities and a set of connections or relations between them. Graph Drawing is concerned with the automatic visualization of graphs in order to make the information useful. That is, a good drawing should be helpful in the application domain where it is used by capturing the relationships in the underlying data. We consider two important problems in automated graph drawing: simultaneous embedding and level planarity. Simultaneous embedding is the problem of drawing multiple graphs while maintaining the readability of each graph independently and preserving the mental map when going from one graph to another. In this case, each graph has the same vertex set (same entities) but different edge sets (different relationships). Level planarity arises in the layout of graphs that contain hierarchical relationships. When drawing graphs in the plane, this translates to a restricted form of planarity where the vertical order of the entities is pre-determined. We consider the computational complexity of the simultaneous embedding problem. In particular, we show that in its generality the simultaneous embedding problem is NP-hard if the edges are drawn as straight-lines. We present algorithms for drawing graphs on predetermined levels, which allow the simultaneous embedding of restricted types of graphs, such as outerplanar graphs, trees and paths. Finally, our practical contribution is a tool that implements known and novel algorithms related to simultaneous embedding and level planarity and can be used both as a visualization software and as an aid to study theoretical problems.
Type:
text; Electronic Dissertation
Keywords:
Computer Science.
Degree Name:
Ph.D.
Degree Level:
doctoral
Degree Program:
Computer Science; Graduate College
Degree Grantor:
University of Arizona
Advisor:
Kobourov, Stephen G.
Committee Chair:
Kobourov, Stephen G.

Full metadata record

DC FieldValue Language
dc.language.isoENen_US
dc.titleSimultaneous Embedding and Level Planarityen_US
dc.creatorEstrella Balderrama, Alejandroen_US
dc.contributor.authorEstrella Balderrama, Alejandroen_US
dc.date.issued2009en_US
dc.publisherThe University of Arizona.en_US
dc.rightsCopyright © is held by the author. Digital access to this material is made possible by the University Libraries, University of Arizona. Further transmission, reproduction or presentation (such as public display or performance) of protected items is prohibited except with permission of the author.en_US
dc.description.abstractGraphs are a common model for representing information consisting of a set of objects or entities and a set of connections or relations between them. Graph Drawing is concerned with the automatic visualization of graphs in order to make the information useful. That is, a good drawing should be helpful in the application domain where it is used by capturing the relationships in the underlying data. We consider two important problems in automated graph drawing: simultaneous embedding and level planarity. Simultaneous embedding is the problem of drawing multiple graphs while maintaining the readability of each graph independently and preserving the mental map when going from one graph to another. In this case, each graph has the same vertex set (same entities) but different edge sets (different relationships). Level planarity arises in the layout of graphs that contain hierarchical relationships. When drawing graphs in the plane, this translates to a restricted form of planarity where the vertical order of the entities is pre-determined. We consider the computational complexity of the simultaneous embedding problem. In particular, we show that in its generality the simultaneous embedding problem is NP-hard if the edges are drawn as straight-lines. We present algorithms for drawing graphs on predetermined levels, which allow the simultaneous embedding of restricted types of graphs, such as outerplanar graphs, trees and paths. Finally, our practical contribution is a tool that implements known and novel algorithms related to simultaneous embedding and level planarity and can be used both as a visualization software and as an aid to study theoretical problems.en_US
dc.typetexten_US
dc.typeElectronic Dissertationen_US
dc.subjectComputer Science.en_US
thesis.degree.namePh.D.en_US
thesis.degree.leveldoctoralen_US
thesis.degree.disciplineComputer Scienceen_US
thesis.degree.disciplineGraduate Collegeen_US
thesis.degree.grantorUniversity of Arizonaen_US
dc.contributor.advisorKobourov, Stephen G.en_US
dc.contributor.chairKobourov, Stephen G.en_US
dc.contributor.committeememberKececioglu, John D.en_US
dc.contributor.committeememberEfrat, Alonen_US
dc.contributor.committeememberWatkins, Joseph C.en_US
dc.identifier.proquest10328en_US
dc.identifier.oclc659751916en_US
All Items in UA Campus Repository are protected by copyright, with all rights reserved, unless otherwise indicated.