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

Hazel Everett (1) , Sylvain Lazard (1) , Giuseppe Liotta (2) , Steve Wismath (3)

1 VEGAS - Effective Geometric Algorithms for Surfaces and Visibility
2 School of Computing
3 Department of Mathematics and Computer Science

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.

Domaines: Géométrie algorithmique [cs.CG]

Hazel Everett, Sylvain Lazard, Giuseppe Liotta, Steve Wismath. Universal Sets of n Points for One-bend Drawings of Planar Graphs with n Vertices. Discrete and Computational Geometry, 2010, 43 (2), pp.272-288. ⟨10.1007/s00454-009-9149-3⟩. ⟨inria-00431769⟩