Embedding Vertices at Points: Few Bends Suffice for Planar Graphs

Kaufmann, Michael and Wiese, Roland (1999) Embedding Vertices at Points: Few Bends Suffice for Planar Graphs. In: Graph Drawing 7th International Symposium, GD’99, September 15-19, 1999, Štirín Castle, Czech Republic , pp. 165-174 (Official URL: http://dx.doi.org/10.1007/3-540-46648-7_17).

Full text not available from this repository.


The existing literature gives efficient algorithms for mapping trees or less restrictively outerplanar graphs on a given set of points in a plane, so that the edges are drawn planar and as straight lines. We relax the latter requirement and allow very few bends on each edge while considering general plane graphs. Our results show two algorithms for mapping four-connected plane graphs with at most one bend per edge and for mapping general plane graphs with at most two bends per edge. Furthermore we give a point set, where for arbitrary plane graphs it is NP-complete to decide whether there is an mapping such that each edge has at most one bend.

Item Type:Conference Paper
Additional Information:10.1007/3-540-46648-7_17
Classifications:G Algorithms and Complexity > G.999 Others
M Methods > M.600 Planar
G Algorithms and Complexity > G.210 Bends
ID Code:325

Repository Staff Only: item control page


Bose, P., On Embedding an Outer-Planar Graph in a Point Set, in: G. DiBattista (ed.), Proc. 5th Intern. Symposium on Graph Drawing (GD '97), LNCS 1353, Springer 1998, pp. 25-36.

Bose, P., M. McAllister, and J. Snoeyink. Optimal algorithms to embed trees in a point set. Journal of Graph Algorithms and Applications 1998.

Castaneda, N. and J. Urrutia., Straight line embeddings of planar graphs on point sets. Proc. 8th Canadian conf. on Comp. Geom., pp. 312-318, 1996.

Chiba, N., and T. Nishizeki, Arboricity and subgraph listing algorithms, SIAM J. Comput. 14 (1985), pp. 210-223.

Chiba, N., and T. Nishizeki, The hamiltonian cycle problem is linear-time solvable for 4-connected planar graphs, J. Algorithms 10 (1989), pp. 189-211.

Di Battista, G., Eades, P., and R. Tamassia, I. G. Tollis, Algorithms for Automatic Graph Drawing: An Annotated Bibliography, Brown Univ., Tech. Rep., 1993.

Garey, M. R., D. S. Johnson, The Rectilinear Steiner Tree Problem is NP-complete, SIAM J. Appl. Math. 32 (1977), pp. 826-834.

Garey, M. R., D. S. Johnson and L. Stockmeyer, Some simplified NP-complete graph problems, Theoret. Comp. Science 1 (1976), pp. 237-267.

Gritzmann, P., Mohar, B., Pach, J. and Pollack, R. Embedding a planar triangulation with vertices at specified points. in: American Mathematical Monthly 98 (1991), pp. 165-166. (Solution to problem E3341).

Ikebe Y., M. Perles, A. Tamura and S. Tokunaga, The rooted tree embedding problem into points in the plane, Discr. and Comp. Geometry 11 (1994), pp. 51-63.

Lengauer, Th., Combinatorial Algorithms for Integrated Circuit Layout, Wiley, 1990.

Pach J. and R. Wenger, Embedding Planar Graphs at Fixed Vertex Locations, in: Sue Whitesides (ed.), Proc. 6th Intern. Symposium on Graph Drawing (GD '98), LNCS 1547, Springer 1999, pp. 263-274.

Pach J. and J. Töröcsik, Layout of rooted trees, in: W. T. Trotter (ed.), Planar Graphs, vol. 9 of DIMACS Series, pages 131-137, 1993.