Persistent Link:
http://hdl.handle.net/10150/195812
Title:
Unlabled Level Planarity
Author:
Fowler, Joe
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:
Consider a graph G with vertex set V in which each of the n vertices is assigned a number from the set {1, ..., k} for some positive integer k. This assignment phi is a labeling if all k numbers are used. If phi does not assign adjacent vertices the same label, then phi partitions V into k levels. In a level drawing, the y-coordinate of each vertex matches its label and the edges are drawn strictly y-monotone. This leads to level drawings in the xy-plane where all vertices with label j lie along the line lj = {(x, j) : x in Reals} and where each edge crosses any of the k horizontal lines lj for j in [1..k] at most once. A graph with such a labeling forms a level graph and is level planar if it has a level drawing without crossings.We first consider the class of level trees that are level planar regardless of their labeling. We call such trees unlabeled level planar (ULP). We describe which trees are ULP and provide linear-time level planar drawing algorithms for any labeling. We characterize ULP trees in terms of two forbidden subdivisions so that any other tree must contain a subtree homeomorphic to one of these. We also provide linear-time recognition algorithms for ULP trees. We then extend this characterization to all ULP graphs with five additional forbidden subdivisions, and provide linear-time recogntion and drawing algorithms for any given labeling.
Type:
text; Electronic Dissertation
Keywords:
Graph drawing; Level planarity; Simultaneous embedding; ULP graphs; Unlabaled level planarity
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.titleUnlabled Level Planarityen_US
dc.creatorFowler, Joeen_US
dc.contributor.authorFowler, Joeen_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.abstractConsider a graph G with vertex set V in which each of the n vertices is assigned a number from the set {1, ..., k} for some positive integer k. This assignment phi is a labeling if all k numbers are used. If phi does not assign adjacent vertices the same label, then phi partitions V into k levels. In a level drawing, the y-coordinate of each vertex matches its label and the edges are drawn strictly y-monotone. This leads to level drawings in the xy-plane where all vertices with label j lie along the line lj = {(x, j) : x in Reals} and where each edge crosses any of the k horizontal lines lj for j in [1..k] at most once. A graph with such a labeling forms a level graph and is level planar if it has a level drawing without crossings.We first consider the class of level trees that are level planar regardless of their labeling. We call such trees unlabeled level planar (ULP). We describe which trees are ULP and provide linear-time level planar drawing algorithms for any labeling. We characterize ULP trees in terms of two forbidden subdivisions so that any other tree must contain a subtree homeomorphic to one of these. We also provide linear-time recognition algorithms for ULP trees. We then extend this characterization to all ULP graphs with five additional forbidden subdivisions, and provide linear-time recogntion and drawing algorithms for any given labeling.en_US
dc.typetexten_US
dc.typeElectronic Dissertationen_US
dc.subjectGraph drawingen_US
dc.subjectLevel planarityen_US
dc.subjectSimultaneous embeddingen_US
dc.subjectULP graphsen_US
dc.subjectUnlabaled level planarityen_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.committeememberKobourov, Stephen G.en_US
dc.contributor.committeememberDowney, Peteren_US
dc.contributor.committeememberEfrat, Alonen_US
dc.contributor.committeememberKececioglu, John D.en_US
dc.identifier.proquest10337en_US
dc.identifier.oclc659751927en_US
All Items in UA Campus Repository are protected by copyright, with all rights reserved, unless otherwise indicated.