Abstract
We give a drawing of K n in 3D 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).
Supported in part by the NSERC Canada.
Chapter PDF
Similar content being viewed by others
References
Bose, P., Czyzowicz, J., Morin, P., Wood, D.R.: The maximum number of edges in a three-dimensional grid-drawing. JGAA 8(1), 21–26 (2004)
Calamoneri, T., Sterbini, A.: 3D straight-line grid drawing of 4-colorable graphs. Information Processing Letters 63(2), 97–102 (1997)
Cohen, R.F., Eades, P., Lin, T., Ruskey, F.: Three-dimensional graph drawing. Algorithmica 17, 199–208 (1997)
Dujmović, V., Morin, P., Wood, D.R.: Layout of graphs with bounded tree-width. SIAM J. of Computing 34(3), 553–579 (2005)
Dujmović, V., Wood, D.R.: Three-dimensional grid drawings with sub-quadratic volume. In: Liotta, G. (ed.) GD 2003. LNCS, vol. 2912, pp. 190–201. Springer, Heidelberg (2004)
Dujmović, V., Wood, D.R.: Stacks, Queues and Tracks: Layouts of Graph Subdivisions. Discrete Math and Theoretical Computer Science 7, 155–202 (2005)
Dyck, B., Joevenazzo, J., Nickle, E., Wilsdon, J., Wismath, S.: Drawing K n in 3D with 2 Bends Per Edge, U. of Lethbridge Tech. Rep. #CS-01-04: 2–7 (January 2004)
Felsner, S., Liotta, G., Wismath, S.: Straight-line drawings on restricted integer grids in two and three dimensions. JGAA 7(4), 363–398 (2003)
Kaufmann, M., Wiese, R.: Embedding vertices at points: few bends suffice for planar graphs. JGAA 6(1), 115–129 (2002)
Morin, P., Wood, D.R.: Three-dimensional 1-bend graph drawings. JGAA 8(3) (2004)
Pach, J., Thiele, T., Tóth, G.: Three-dimensional grid drawings of graphs. In: DiBattista, G. (ed.) GD 1997. LNCS, vol. 1353, pp. 47–51. Springer, Heidelberg (1997)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Devillers, O., Everett, H., Lazard, S., Pentcheva, M., Wismath, S.K. (2006). Drawing K n in Three Dimensions with One Bend Per Edge. In: Healy, P., Nikolov, N.S. (eds) Graph Drawing. GD 2005. Lecture Notes in Computer Science, vol 3843. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11618058_8
Download citation
DOI: https://doi.org/10.1007/11618058_8
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-31425-7
Online ISBN: 978-3-540-31667-1
eBook Packages: Computer ScienceComputer Science (R0)