Contact Representations of Graphs
Date Issued
2015
Date
2015
Author(s)
Chang
Abstract
Graph represents one of the most popular abstract models in describing complex science and engineering problems. Graph drawing refers to the process of displaying an abstract graph in 2D or 3D, allowing the structure as well as the meaning of the graph to be understood better and easier. As a consequence, the design of graph drawing algorithms has become an emerging and fast growing research area in computer science. Among problems of interest in the graph drawing community, the topic of contact representations of graphs has received increasing attention over the years. Given a graph, a contact representation of the graph is to map each vertex of the graph to a geometric object in 2D or 3D so that two vertices are adjacent iff their corresponding objects ""touch"". A rectilinear dual, a classic drawing style which has found applications in VLSI floor-planning, requires that each vertex be drawn as a rectilinear polygon, adjacency in a graph correspond to side-contact in the drawing, and all rectilinear polygons together form a partition of a rectangle. In the first half of the thesis, we investigate a variety of shape constraints in rectilinear duals. As convex objects tend to be visually more pleasing, the drawing style orthogonally convex drawing is proposed and investigated. In addition, we study rectilinear duals using a restricted set of shapes, in order to understand the power and the limitation of different shapes in rectilinear duals. We determine the optimal polygonal complexity of T-free rectilinear dual, justifying the intuition that T-shape is the most useful 8-sided polygon. In the second half of the thesis, we study possible extensions and generalizations of rectilinear duals beyond the 2D rectilinear setting. To accommodate convex polygons, the drawing style convex polygonal dual is proposed and investigated. We demonstrate several new techniques and fixed-parameter tractability results to deal with this drawing style. We also propose and investigate a new drawing style called 3D floorplan, using rectilinear polyhedra as building blocks. We show that every chordal graph admits a 3D-floorplan which uses only two layers and is also capable of realizing any volume-assignment to its constituent polyhedra. In summary, the thesis provides a variety of new techniques and new perspectives within the framework of contact representations of graphs. We hope that this study could lead to a better understanding of contact graph representations - an exciting and challenging topic in graph drawing.
Subjects
graph drawing
contact representation
planar graph
cartogram
floorplan
Type
thesis
File(s)![Thumbnail Image]()
Loading...
Name
ntu-104-R02921039-1.pdf
Size
23.32 KB
Format
Adobe PDF
Checksum
(MD5):29caadb14204c3b2fbba42af49f25806