Universal Sets of n Points for 1-bend Drawings of Planar Graphs with n Vertices

Everett, Hazel and Lazard, Sylvain and Liotta, Giuseppe and Wismath, Stephen (2008) Universal Sets of n Points for 1-bend Drawings of Planar Graphs with n Vertices. In: Graph Drawing 15th International Symposium, GD 2007, September 24-26, 2007, Sydney, Australia , pp. 345-351 (Official URL: http://dx.doi.org/10.1007/978-3-540-77537-9_34).

Full text not available from this repository.

Abstract

This paper shows that any planar graph with $n$ vertices can be point-set embedded with at most one bend per edge on a universal set of $n$ points in the plane. An implication of this result is that any number of planar graphs admit a simultaneous embedding without mapping with at most one bend per edge.

Item Type:Conference Paper
Additional Information:10.1007/978-3-540-77537-9_34
Classifications:G Algorithms and Complexity > G.210 Bends
ID Code:850

Repository Staff Only: item control page

References

P. Braß, E. Cenek, C. A. Duncan, A. Efrat, C. Erten, D. Ismailescu, S. G. Kobourov, A. Lubiw, and J. S. B. Mitchell. On Simultaneous planar graph embeddings. Comput. Geom., 36(2):117-130, 2007.

M. Chrobak and H. Karloff. A lower bound on the size of universal sets for planar graphs. SIGACT News, 20(4):83-86, 1989.

H. de Fraysseix, J. Pach, and R. Pollack. How to draw a planar graph on a grid. Combinatorica, 10:41-51, 1990.

E. Di Giacomo, W. Didimo, G. Liotta, and S. K. Wismath. Curve-constrained drawings of planar graphs. Computational Geometry, 30:1-23, 2005.

P. Gritzmann, B. Mohar, J. Pach, and R. Pollack. Embedding a planar triangulation with vertices at specified points. Amer. Math. Monthly, 98(2):165-166, 1991.

M. Kaufmann and R. Wiese. Embedding vertices at points: Few bends suffice for planar graphs. Journal of Graph Algorithms and Applications, 6(1):115-129, 2002.

M. Kurowski. A 1.235 lower bound on the number of points needed to draw all n-vertex planar graphs. Inf. Process. Lett., 92(2):95-98, 2004.

J. Pach and R. Wenger. Embedding planar graphs at fixed vertex locations. Graph and Combinatorics, 17:717-728, 2001.

W. Schnyder. Embedding planar graphs on the grid. In Proc. 1st ACM-SIAM Sympos. Discrete Algortihms (SODA '90), pages 138-148, 1990.