Accession Number:

ADA318526

Title:

Proximity Drawings of Outerplanar Graphs (Preliminary Version).

Descriptive Note:

Technical rept.,

Corporate Author:

BROWN UNIV PROVIDENCE RI DEPT OF COMPUTER SCIENCE

Personal Author(s):

Report Date:

1996-06-01

Pagination or Media Count:

15.0

Abstract:

A proximity drawing of a graph is one in which pairs of adjacent vertices are drawn relatively close together according to some proximity measure while pairs of non-adjacent vertices are drawn relatively far apart. The fundamental question concerning proximity drawability is Given a graph G and a definition of proximity, is it possible to construct a proximity drawing of G We consider this question for outerplanar graphs with respect to an infinite family of proximity drawings called beta-drawings. These drawings include as special cases the well-known Gabriel drawings when beta 1, and relative neighborhood drawings when beta 2. We first show that all biconnected outerplanar graphs are beta-drawable for all values of beta such that 1 beta 2. As a side effect, this result settles in the affirmative a conjecture by Lubiw and Sleumer, that any biconnected outerplanar graph admits a Gabriel drawing. We then show that there exist biconnected outerplanar graphs that do not admit any convex beta-drawing for beta between 1 and 2. We also provide upper bounds on the maximum number of biconnected components sharing the same cut-vertex in a beta-drawable connected outerplanar graph. This last result is generalized to arbitrary connected planar graphs and is the first non-trivial characterization of connected beta-drawable graphs. Finally, a weaker definition of proximity drawings is applied and we show that all connected outerplanar graphs are drawable under this definition.

Subject Categories:

  • Numerical Mathematics

Distribution Statement:

APPROVED FOR PUBLIC RELEASE