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.
| Identifer | oai:union.ndltd.org:arizona.edu/oai:arizona.openrepository.com:10150/556963 |
| Date | January 2015 |
| Creators | Alam, Muhammad Jawaherul |
| Contributors | Kobourov, Stephen G., Kobourov, Stephen G., Efrat, Alon, Glickenstein, David, Kececioglu, John |
| Publisher | The University of Arizona. |
| Source Sets | University of Arizona |
| Language | en_US |
| Detected Language | English |
| Type | text, Electronic Dissertation |
| 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. |
Page generated in 0.0022 seconds