Computing B-drawings of 2-outerplane graphs

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.