Drawing K_n in Three Dimensions with One Bend per Edge

Devillers, Olivier and Everett, Hazel and Lazard, Sylvain and Pentcheva, Maria and Wismath, Stephen (2006) Drawing K_n in Three Dimensions with One Bend per Edge. In: Graph Drawing 13th International Symposium, GD 2005, September 12-14, 2005, Limerick, Ireland , pp. 83-88 (Official URL: http://dx.doi.org/10.1007/11618058_8).

Full text not available from this repository.

Abstract

We give a drawing of K_n 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}). This represents a significant improvement over previous drawings in this model.

Item Type:Conference Paper
Additional Information:10.1007/11618058_8
Classifications:G Algorithms and Complexity > G.070 Area / Edge Length
G Algorithms and Complexity > G.210 Bends
P Styles > P.060 3D
ID Code:682

Repository Staff Only: item control page

References

P. Bose, J. Czyzowicz, P. Morin and D. R. Wood.: The maximum number of edges in a three-dimensional grid-drawing, JGAA, 8(1):21--26, 2004.

T. Calamoneri and A. Sterbini.: 3D straight-line grid drawing of 4-colorable graphs, Information Processing Letters 63(2):97--102, 1997.

R. F. Cohen, P. Eades, T. Lin, and F. Ruskey.: Three-dimensional graph drawing, Algorithmica, 17:199--208, 1997.

V. Dujmovic, P. Morin, and D. R. Wood.: Layout of graphs with bounded tree-width, SIAM J. of Computing, 34(3)553-579, 2005.

V. Dujmovic, and D. R. Wood.: Three-dimensional grid drawings with sub-quadratic volume, (GD '03), LNCS 2912:190--201, Springer-Verlag, 2004.

V. Dujmovic, and D. R. Wood.: Stacks, Queues and Tracks: Layouts of Graph Subdivisions, Discrete Math and Theoretical Computer Science, 7:155-202, 2005.

B. Dyck, J. Joevenazzo, E. Nickle, J.Wilsdon, and S. Wismath.Drawing K_n in 3D with 2 Bends Per Edge, U. of Lethbridge Tech Rep #CS-01-04: 2--7, Jan 2004.

S. Felsner, G. Liotta, S. Wismath.: Straight-line drawings on restricted integer grids in two and three dimensions, JGAA, 7(4):363--398, 2003.

M. Kaufmann and R.Wiese.: Embedding vertices at points: few bends suffice for planar graphs, JGAA, 6(1):115--129, 2002.

P. Morin and D. R. Wood.: Three-dimensional 1-bend graph drawings, JGAA, 8(3), 2004.

J. Pach, T. Thiele, and G.Toth.: Three-dimensional grid drawings of graphs, (GD '97), LNCS, 1353:47--51, Springer-Verlag, 1997.