With PQDT Open, you can read the full text of open access dissertations and theses free of charge.
About PQDT Open
Search
This thesis is about representations of planar graphs. The vertices of a graph can be represented by points in the plane, two points are connected by a line segment if and only if the two vertices are adjacent. This is called a classical drawing of a graph. Another way of representing graphs is as the contact or intersection representation of geometric objects. One famous example of contact representations is the circle contact representation. In this representation each vertex is represented by a circle in the plane, the circles are internally disjoint and two circles touch if and only if the vertices are adjacent. In this work we consider both a classical drawing with some restrictions as well as two types of contact representations. In Chapter 2 we consider a drawing in the classical setting, i.e. vertices are points in the plane and edges are straight-lines between two points. We ask which graphs admit a straight-line drawing such that all the faces are triangles, this is denoted by Straight-Line Triangle Representation. To the best of our knowledge, it is still open whether, given a planar graph G, the question "Does G admit a straight-line triangle representation?" belongs to P. We will give two characterizations of graphs that admit a straight-line triangle representation. However, we are not aware of an efficient way to check whether a given graph satisfies the conditions. On the positive side, we identify several classes of graphs for which all graphs admit a straight-line triangle representation. In Chapter 3 the question is considered in its dual form: we now ask for a representation in which the vertices are triangles and the edges are side-contacts between two triangles. Such a representation is called a Touching Triangle Representation. We have been able to characterize the biconnected outerplanar graphs that admit a touching triangle representation in a convex polygon. Secondly, we show that every Halin graph admits a touching triangle representation in a triangle. In Chapter 4 the objects that represent vertices are grid-paths and we study contact representations of paths in a grid. The class of graphs that admit a grid-path contact representation is precisely the class of planar (2,0)-sparse graphs. We will give a combinatorial characterization of grid-path contact representations. The interesting question about this representation is whether we can minimize the number of bends, locally as well as globally. Using the combinatorial characterization, we give bounds on the number of bends per vertex, that suffice to represent (2,l)-tight planar graphs for different values of l. In Chapter 5 we will give the current status of the problems addressed in this thesis and the open problems that we have encountered along the way.
Advisor: | Felsner, Stefan |
Commitee: | |
School: | Technische Universitaet Berlin (Germany) |
School Location: | Germany |
Source: | DAI-C 81/1(E), Dissertation Abstracts International |
Source Type: | DISSERTATION |
Subjects: | Mathematics |
Keywords: | Contact representations, Planar graphs |
Publication Number: | 10695952 |
ISBN: | 9781392713310 |