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

摘要

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. Keywords Graph drawing - Universal point sets - One-bend drawings - Simultaneous embeddings Research supported by NSERC and the MIUR Project “MAINSTREAM: Algorithms for Massive Information Structures and Data Streams.” Work initiated during the “Workshop on Graph Drawing and Computational Geometry,” Bertinoro, Italy, March 2007. We are grateful to the other participants and, in particular, to W. Didimo and E. Di Giacomo for useful discussions. An earlier version of this paper was presented at the 15th International Symposium on Graph Drawing, GD 2007.