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.
|School:||Technische Universitaet Berlin (Germany)|
|Source:||DAI-C 81/1(E), Dissertation Abstracts International|
|Keywords:||Contact representations, Planar graphs|
Copyright in each Dissertation and Thesis is retained by the author. All Rights Reserved
The supplemental file or files you are about to download were provided to ProQuest by the author as part of a
dissertation or thesis. The supplemental files are provided "AS IS" without warranty. ProQuest is not responsible for the
content, format or impact on the supplemental file(s) on our system. in some cases, the file type may be unknown or
may be a .exe file. We recommend caution as you open such files.
Copyright of the original materials contained in the supplemental file is retained by the author and your access to the
supplemental files is subject to the ProQuest Terms and Conditions of use.
Depending on the size of the file(s) you are downloading, the system may take some time to download them. Please be