Proximity Drawings of Outerplanar Graphs (extended abstract)

Lenhart, William J. and Liotta, Giuseppe (1997) Proximity Drawings of Outerplanar Graphs (extended abstract). In: Symposium on Graph Drawing, GD '96, September 18-20, 1996 , pp. 286-302(Official URL:

Full text not available from this repository.


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 \le \beta \le 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 than show that there exist biconnectedouterplanar graphs that do not admit any convex \beta -drawing for 1 \le \beta \le 2. We also provide upper bounds on the maximum nuber of biconnected components sharing the same cut-vertex in a \beta -drawable connected outerplanar graphs. 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.

Item Type: Conference Paper
Additional Information: 10.1007/3-540-62495-3_55
Classifications: P Styles > P.999 Others
P Styles > P.540 Planar

Actions (login required)

View Item View Item