Abstract:
One of the relatively new graph drawing problems is the proximity drawing of graphs.
A proximity drawing of a plane graph G is a straight-line drawing of G with the additional
geometric constraint that two vertices of G are adjacent if and only if the well-defined
"proximity region" of these two vertices does not contain any other vertex. In general,
a proximity drawing of a graph has some appealing features. For example, the group
of vertices which are adjacent to each other tend to stay close together in the proximity
drawing and the vertices that are nonadjacent tend to stay relatively far apart from each
other. These underlying features of a proximity drawing of a graph have made it useful
in many practical application areas. One class of parameterized proximity drawings is
the ,6-drawing, where the value of the parameter ,6 can be any nonnegative real number
including 00. The problem of whether a class of graphs is ,6-drawable, for some value of,6,
has been studied for two classes of graphs, namely trees and outer planar graphs. However,
for larger classes of graphs the problem of ,6-drawability is still an open problem. In this
thesis we concentrate on the problem of ,6-drawings of 2-outerplane graphs for 1 < ,6 < 2.
We provide a characterization of a subclass of biconnected 2-outerplane graphs for having
a ,6-drawing for the specified range of ,6 values. We provide a drawing algorithm as well.
We also identify a subclass of biconnected 2-outerplane graphs that are not ,6-drawable
for 1 < ,6 < 2.
