Algorithmic Aspects of Constrained Unit Disk Graphs

ID
TR-96-15
Authors
Heinz Breu
Publishing date
September 1996
Length
369 pages
Abstract
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 NP-complete 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, tau-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 tau. This thesis studies algorithmic and structural aspects of varying the value tau for tau-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" (tau is small) or "discrete" (the number of possible y-coordinates for the disks is small). Note again that indifference graphs are the thinnest (tau=0) and most discrete (one y-coordinate) of the nontrivial tau-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.