Computational problems on graphs often arise in two- or three-dimensional geometric
contexts. Such problems include assigning channels to radio transmitters (graph colouring),
physically routing traces on a printed circuit board (graph drawing), and modelling
molecules. It is reasonable to expect that natural graph problems have more efficient
solutions when restricted to such geometric graphs. Unfortunately, many familiar NPcomplete
problems remain NP-complete on geometric graphs.
Indifference graphs arise in a one-dimensional geometric context; they are the intersection
graphs of unit intervals on the line. Many NP-complete problems on arbitrary
graphs do have efficient solutions on indifference graphs. Yet these same problems remain
NP-complete for the intersection graphs of unit disks in the plane (unit disk graphs), a
natural two-dimensional generalization of indifference graphs. What accounts for this
situation, and how can algorithms be designed to deal with it?
To study these issues, this thesis identifies a range of subclasses of unit disk graphs
in which the second spatial dimension is gradually, introduced. More specifically, τ-strip graphs "interpolate" between unit disk graphs and indifference graphs; they are the
intersection graphs of unit-diameter disks whose centres are constrained to lie in a strip of
thickness τ. This thesis studies algorithmic and structural aspects of varying the value τ
for τ-strip graphs.
The thesis takes significant steps towards characterizing, recognizing, and laying out
strip graphs. We will also see how to develop algorithms for several problems on strip
graphs, and how to exploit their geometric representation. In particular, we will see that
problems become especially tractable when the strips are "thin" (τ is small) or "discrete" (the number of possible y-coordinates for the disks is small). Note again that indifference
graphs are the thinnest (τ = 0) and most discrete (one y-coordinate) of the nontrivial
τ-strip graphs.
The immediate results of this research concern algorithms for a specific class of graphs.
The real contribution of this research is the elucidation of when and where geometry can
be exploited in the development of efficient graph theoretic algorithms. / Science, Faculty of / Computer Science, Department of / Graduate
| Identifer | oai:union.ndltd.org:UBC/oai:circle.library.ubc.ca:2429/6282 |
| Date | 05 1900 |
| Creators | Breu, Heinz |
| Source Sets | University of British Columbia |
| Language | English |
| Detected Language | English |
| Type | Text, Thesis/Dissertation |
| Format | 15033516 bytes, application/pdf |
| Rights | For non-commercial purposes only, such as research, private study and education. Additional conditions apply, see Terms of Use https://open.library.ubc.ca/terms_of_use. |
Page generated in 0.0108 seconds