
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) : Lenhart, William ; Liotta, Giuseppe
PDF Url : ADA318526
Report Date : JUN 1996
Pagination or Media Count : 15
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 nonadjacent 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 betadrawings. These drawings include as special cases the wellknown Gabriel drawings (when beta = 1), and relative neighborhood drawings (when beta = 2). We first show that all biconnected outerplanar graphs are betadrawable 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 betadrawing for beta between 1 and 2. We also provide upper bounds on the maximum number of biconnected components sharing the same cutvertex in a betadrawable connected outerplanar graph. This last result is generalized to arbitrary connected planar graphs and is the first nontrivial characterization of connected betadrawable graphs. Finally, a weaker definition of proximity drawings is applied and we show that all connected outerplanar graphs are drawable under this definition.
Descriptors : *GRAPHS, COMPUTER GRAPHICS, APPLIED MATHEMATICS, ENGINEERING DRAWINGS, PROJECTIVE GEOMETRY, LINES(GEOMETRY), PLANE GEOMETRY.
Subject Categories : Numerical Mathematics
Distribution Statement : APPROVED FOR PUBLIC RELEASE