Drawing Kn in Three Dimensions with One Bend per Edge

Olivier Devillers (1) , Hazel Everett (2) , Sylvain Lazard (2) , Maria Pentcheva (2) , Steve Wismath (3)

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

We give a drawing of Kn in three dimensions in which vertices are placed at integer grid points and edges are drawn crossing-free with at most one bend per edge in a volume bounded by $O(n^{2.5})$.

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

Olivier Devillers, Hazel Everett, Sylvain Lazard, Maria Pentcheva, Steve Wismath. Drawing Kn in Three Dimensions with One Bend per Edge. Journal of Graph Algorithms and Applications, 2006, 10 (2), pp.287-295. ⟨inria-00103923⟩