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, Berkeley, California, USA , pp. 286-302 (Official URL: http://dx.doi.org/10.1007/3-540-62495-3_55).

Full text not available from this repository.

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 \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
ID Code:196

Repository Staff Only: item control page

References

H. Alt, M. Godau, and S.H. Whitesides. Universal 3-dimensional visibility representations for graphs. In Graph Drawing (Proc. GD '95), vol. 1027 of LNCS, pages 8-19. Springer-Verlag, 1996.

P. Bose, G. Di Battista, W. Lenhart, and G. Liotta. Proximity constraints and representable trees. In Graph Drawing (Proc. GD '95), vol. 1027 of LNCS, Springer-Verlag, 1996.

P. Bose, W. Lenhart, and G. Liotta. Charakterizing proximity trees. Technical Report TR- SOCS 93.9, School of Computer Science, McGill University, 1993.

M. Chrobak, M.T. Goodrich, and R. Tamassia. Convex drawings of graphs in two and three dimensions. In Proc. 12th Annu. ACM Sympos. Comput. Geom., pages 319-328, 1996.

G. Di Battista, W. Lenhart, and G. Liotta. Proximity drawability: A survey. In Graph Drawing (Proc. GD '95), vol. 1027 of LNCS, Springer-Verlag, 1996.

G. Di Battista, and G. Liotta. Computing proximity drawings of trees in 3-d space. In WADS (Proc. WADS '95). Springer-Verlag, 1995.

G. Di Battista, G. Liotta, and S.H. Whitesides. The strength of weak proximity. In Graph Drawing (Proc. GD '95), vol. 1027 of LNCS, pages 178-189, Springer-Verlag, 1996.

P. Eades and P. Garvau. Drawing stressed planar graphs in three dimensions. In Graph Drawing (Proc. GD '95), vol. 1027 of LNCS, pages 212-223, Springer-Verlag, 1996.

P. Eades and S.H. Whitesides. The realization problem for euclidian minimum spanning trees is np-hard. In Proc. ACM Symp. on Comp. Geom., 1994.

S. Fekete, M. Houle, and S.H. Whitesides. New results on a visibility representation of graphs in 3d. In Graph Drawing (Proc. GD '95), vol. 1027 of LNCS, pages 234-241, Springer-Verlag, 1996.

K.R. Gabriel and R.R. Sokal. A new statistical approach to geographical analysis. Systematic Zoology. 18:54-64, 1969.

J.W. Jaromczyk and G.T. Toussaint. Relative neighborhood graphs and their relatives. In Proceedings of the IEEE, 80, pages 1502-1517, 1992.

D.G. Kirkpatrick and J.D. Radke. A framework for computational morphology. In G.T. Toussaint, editor, Computational Geometry, pages 217-248. Elsevier, Amsterdam, 1985.

W. Lenhart and G. Liotta. Drawing outerplanar minimum weighttriangulations. Inform. Process. Lett., 6(12):253-260, 1996.

A. Lubiw and N. Sleumer. All maximal outerplanar graphs are relative neighborhood graphs. In Proc. 5th CCCG, pages 198-203, 1993.

D.W. Matula and R.R. Sokal. Properties of gabriel graphs relevant to geographic variation research and the clustering of points in the plane. Geographical analysis, 12(3):205-222, 1980.

N. Sleumer. Outerplanar graphs as proximity graphs. Master's thesis, University of Waterloo, Waterloo, Canada, 1993.

G. Toussaint. The relative neighborhood graph of a finite planar set. Pattern Recognition, 12:229-260, 1980.

W.T. Tutte. Connectivity in graphs. Oxford University Press, 1972.