Optimal 3D Angular Resolution for Low-Degree Graphs

Eppstein, David and Löffler, Maarten and Mumford, Elena and Nöllenburg, Martin (2011) Optimal 3D Angular Resolution for Low-Degree Graphs. In: Graph Drawing 18th International Symposium, GD 2010, September 21-24, 2010, Konstanz, Germany , pp. 208-219 (Official URL: http://dx.doi.org/10.1007/978-3-642-18469-7_19).

Full text not available from this repository.


We show that every graph of maximum degree three can be drawn in three dimensions with at most two bends per edge, and with 120° angles between any two edge segments meeting at a vertex or a bend. We show that every graph of maximum degree four can be drawn in three dimensions with at most three bends per edge, and with 109.5° angles, i.e., the angular resolution of the diamond lattice, between any two edge segments meeting at a vertex or bend.

Item Type:Conference Paper
Additional Information:10.1007/978-3-642-18469-7_19
Classifications:P Styles > P.060 3D
ID Code:1207

Repository Staff Only: item control page


Angelini, P., Cittadini, L., Di Battista, G., Didimo, W., Frati, F., Kaufmann, M., Symvonis, A.: On the perspectives opened by right angle crossing drawings. In: Eppstein, D., Gansner, E.R. (eds.) GD 2009. LNCS, vol. 5849, pp. 21–32. Springer, Heidelberg (2010), doi:10.1007/978-3-642-11805-0_5

Biedl, T.C., Bose, P., Demaine, E.D., Lubiw, A.: Efficient algorithms for Petersen’s matching theorem. Journal of Algorithms 38(1), 110–134 (2001), doi:10.1006/jagm.2000.1132

Biedl, T.C., Thiele, T., Wood, D.R.: Three-dimensional orthogonal graph drawing with optimal volume. Algorithmica 44(3), 233–255 (2006), doi:10.1007/s00453-005-1148-z

Carlson, J., Eppstein, D.: Trees with convex faces and optimal angles. In: Kaufmann, M., Wagner, D. (eds.) GD 2006. LNCS, vol. 4372, pp. 77–88. Springer, Heidelberg (2007)

Clare, B.W., Kepert, D.L.: The closest packing of equal circles on a sphere. Proc. Roy. Soc. London A 405(1829), 329–344 (1986), doi:10.1098/rspa.1986.0056

Demaine, E.D.: Problem 46: 3D minimum-bend orthogonal graph drawings. The Open Problems Project. Posed by David R. Wood at the CCCG, open-problem session (2002), http://maven.smith.edu/~orourke/TOPP/P46.html

Didimo, W., Eades, P., Liotta, G.: Drawing graphs with right angle crossings. In: Dehne, F., Gavrilova, M., Sack, J.-R., Tóth, C.D. (eds.) WADS 2009. LNCS, vol. 5664, pp. 206–217. Springer, Heidelberg (2009), doi:10.1007/978-3-642-03367-4_19

Dujmović, V., Gudmundsson, J., Morin, P., Wolle, T.: Notes on large angle crossing graphs. arXiv:0908.3545 (2009)

Duncan, C.A., Eppstein, D., Kobourov, S.G.: The geometric thickness of low degree graphs. In: Proc. 20th ACM Symp. Computational Geometry (SoCG 2004), pp. 340–346 (2004), doi:10.1145/997817.997868, arXiv:cs.CG/0312056

Eades, P., Symvonis, A., Whitesides, S.: Three-dimensional orthogonal graph drawing algorithms. Discrete Applied Mathematics 103(1-3), 55–87 (2000), doi:10.1016/S0166-218X(00)00172-4

Eiglsperger, M., Fekete, S.P., Klau, G.W.: Orthogonal graph drawing. In: Kaufmann, M., Wagner, D. (eds.) Drawing Graphs. LNCS, vol. 2025, pp. 121–171. Springer, Heidelberg (2001), doi:10.1007/3-540-44969-8_6

Eppstein, D.: Isometric diamond subgraphs. In: Tollis, I.G., Patrignani, M. (eds.) GD 2008. LNCS, vol. 5417, pp. 384–389. Springer, Heidelberg (2009), doi:10.1007/978-3-642-00219-9_37

Garg, A., Tamassia, R.: Planar drawings and angular resolution: algorithms and bounds. In: van Leeuwen, J. (ed.) ESA 1994. LNCS, vol. 855, pp. 12–23. Springer, Heidelberg (1994), doi:10.1007/BFb0049393

Gutwenger, C., Mutzel, P.: Planar polyline drawings with good angular resolution. In: Whitesides, S.H. (ed.) GD 1998. LNCS, vol. 1547, pp. 167–182. Springer, Heidelberg (1999), doi:10.1007/3-540-37623-2_13

Huang, W., Hong, S.-H., Eades, P.: Effects of crossing angles. In: Proc. IEEE Pacific Visualization Symp., pp. 41–46 (2008), doi:10.1109/PACIFICVIS.2008.4475457

Malitz, S.: On the angular resolution of planar graphs. In: Proc. 24th ACM Symp. Theory of Computing (STOC 1992), pp. 527–538 (1992), doi:10.1145/129712.129764

Petersen, J.: Die Theorie der regulären Graphs. Acta Math. 15(1), 193–220 (1891), doi:10.1007/BF02392606

Tammes, P.M.L.: On the origin of the number and arrangement of the places of exit on the surface of pollen grains. Ree. Trav. Bot. Néerl. 27, 1–82 (1930)

Wood, D.R.: Optimal three-dimensional orthogonal graph drawing in the general position model. Theor. Comput. Sci. 299(1-3), 151–178 (2003), doi:10.1016/S0304-3975(02)00044-0