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 1820, 1996 , pp. 286302(Official URL: http://dx.doi.org/10.1007/3540624953_55). Full text not available from this repository.
Official URL: http://dx.doi.org/10.1007/3540624953_55
AbstractA 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 \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 cutvertex in a \beta drawable connected outerplanar graphs. This last result is generalized to arbitrary connected planar graphs and is the first nontrivial 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.
Actions (login required)
