Persistent Link:
http://hdl.handle.net/10150/556963
Title:
Contact Representations of Graphs in 2D and 3D
Author:
Alam, Muhammad Jawaherul
Issue Date:
2015
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:
We study contact representations of graphs in the plane and in 3D space, where vertices are represented by polygons or polyhedra and each edge is represented by a common boundary between two polygons or polyhedra. In the weighted version of the problem, we find contact representations with the additional restriction that the areas for the polygons or the volumes for the polyhedra realize some pre-specified value for the vertices. We address different variants of the problem depending on the types of polygons or polyhedra (convex or non-convex, axis-aligned or not), types of contacts (proper contacts with common boundaries of non-zero lengths in 2D or non-zero areas in 3D or improper contacts where common boundaries of zero lengths or areas are allowed), and whether holes are allowed in the representation or not. In the plane we mainly focus on the weighted version of the problem. We find optimal (in terms of polygonal complexity) contact representations for planar graphs (both for axis-aligned and non-axis-aligned polygons) and some subclasses of planar graphs. With non-axis-aligned polygons we show that non-convex polygons with 4 sides are sometimes necessary and always sufficient for proportional contact representation of a planar graph, when point contacts are allowed; otherwise for proper contacts 7-sided polygons are sometimes necessary and always sufficient. We give a linear-time algorithm in each case to compute the optimal representation. We also give quadratic-time algorithms to construct optimal proportional contact representations for (2, 0)-sparse graphs (with triangles for improper contacts and with convex quadrilaterals for proper contacts). For maximal outerplanar graphs proportional contact representation with triangles can also be computed in linear time. In case only axis-aligned polygons are used, we show that 8 sides are sometimes necessary and always sufficient for a planar graph. While we do not have a polynomial-time algorithm to construct such a representation, we give a linear-time algorithm to compute representation with 10-sided axis-aligned polygons. We also give linear-time construction algorithms for optimal proportional contact representations with 8-sided polygons for planar 3-trees and Hamiltonian maximal planar graphs, and with rectangles for maximal outerplanar graphs. For contact representation with 3D polyhedra, we consider both the weighted and the unweighted variants of the problem for both planar and non-planar graphs and have some preliminary results. We find several subclasses of planar graphs that have contact representations using cubes or proportional boxes. We also consider (improper) contact representations using tetrahedra, and show that planar graphs, complete bipartite and tripartite graphs, and complete graphs with at most 10 vertices have contact representations with tetrahedra. We also addressed variants of this problem using only unit regular tetrahedra or considering contacts only between apices of the tetrahedra or using both restrictions.
Type:
text; Electronic Dissertation
Keywords:
Cartograms; Contact Representations; Graphs; Computer Science; Algorithms
Degree Name:
Ph.D.
Degree Level:
doctoral
Degree Program:
Graduate College; Computer Science
Degree Grantor:
University of Arizona
Advisor:
Kobourov, Stephen G.

Full metadata record

DC FieldValue Language
dc.language.isoen_USen
dc.titleContact Representations of Graphs in 2D and 3Den_US
dc.creatorAlam, Muhammad Jawaherulen
dc.contributor.authorAlam, Muhammad Jawaherulen
dc.date.issued2015en
dc.publisherThe University of Arizona.en
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
dc.description.abstractWe study contact representations of graphs in the plane and in 3D space, where vertices are represented by polygons or polyhedra and each edge is represented by a common boundary between two polygons or polyhedra. In the weighted version of the problem, we find contact representations with the additional restriction that the areas for the polygons or the volumes for the polyhedra realize some pre-specified value for the vertices. We address different variants of the problem depending on the types of polygons or polyhedra (convex or non-convex, axis-aligned or not), types of contacts (proper contacts with common boundaries of non-zero lengths in 2D or non-zero areas in 3D or improper contacts where common boundaries of zero lengths or areas are allowed), and whether holes are allowed in the representation or not. In the plane we mainly focus on the weighted version of the problem. We find optimal (in terms of polygonal complexity) contact representations for planar graphs (both for axis-aligned and non-axis-aligned polygons) and some subclasses of planar graphs. With non-axis-aligned polygons we show that non-convex polygons with 4 sides are sometimes necessary and always sufficient for proportional contact representation of a planar graph, when point contacts are allowed; otherwise for proper contacts 7-sided polygons are sometimes necessary and always sufficient. We give a linear-time algorithm in each case to compute the optimal representation. We also give quadratic-time algorithms to construct optimal proportional contact representations for (2, 0)-sparse graphs (with triangles for improper contacts and with convex quadrilaterals for proper contacts). For maximal outerplanar graphs proportional contact representation with triangles can also be computed in linear time. In case only axis-aligned polygons are used, we show that 8 sides are sometimes necessary and always sufficient for a planar graph. While we do not have a polynomial-time algorithm to construct such a representation, we give a linear-time algorithm to compute representation with 10-sided axis-aligned polygons. We also give linear-time construction algorithms for optimal proportional contact representations with 8-sided polygons for planar 3-trees and Hamiltonian maximal planar graphs, and with rectangles for maximal outerplanar graphs. For contact representation with 3D polyhedra, we consider both the weighted and the unweighted variants of the problem for both planar and non-planar graphs and have some preliminary results. We find several subclasses of planar graphs that have contact representations using cubes or proportional boxes. We also consider (improper) contact representations using tetrahedra, and show that planar graphs, complete bipartite and tripartite graphs, and complete graphs with at most 10 vertices have contact representations with tetrahedra. We also addressed variants of this problem using only unit regular tetrahedra or considering contacts only between apices of the tetrahedra or using both restrictions.en
dc.typetexten
dc.typeElectronic Dissertationen
dc.subjectCartogramsen
dc.subjectContact Representationsen
dc.subjectGraphsen
dc.subjectComputer Scienceen
dc.subjectAlgorithmsen
thesis.degree.namePh.D.en
thesis.degree.leveldoctoralen
thesis.degree.disciplineGraduate Collegeen
thesis.degree.disciplineComputer Scienceen
thesis.degree.grantorUniversity of Arizonaen
dc.contributor.advisorKobourov, Stephen G.en
dc.contributor.committeememberKobourov, Stephen G.en
dc.contributor.committeememberEfrat, Alonen
dc.contributor.committeememberGlickenstein, Daviden
dc.contributor.committeememberKececioglu, Johnen
All Items in UA Campus Repository are protected by copyright, with all rights reserved, unless otherwise indicated.