Abstract
We introduce the notion of Lombardi graph drawings, named after the American abstract artist Mark Lombardi. In these drawings, edges are represented as circular arcs rather than as line segments or polylines, and the vertices have perfect angular resolution: the edges are equally spaced around each vertex. We describe algorithms for finding Lombardi drawings of regular graphs, graphs of bounded degeneracy, and certain families of planar graphs.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Aichholzer, O., Aigner, W., Aurenhammer, F., Dobiášová, K.Č., Jüttler, B.: Arc triangulations. In: Proc. 26th Eur. Worksh. Comp. Geometry (EuroCG 2010), Dortmund, Germany, pp. 17–20 (2010)
Alon, N.: A simple algorithm for edge-coloring bipartite multigraphs. Information Processing Letters 85(6), 301–302 (2003), doi:10.1016/S0020-0190(02)00446-5
Baur, M., Brandes, U.: Crossing reduction in circular layouts. In: Hromkovič, J., Nagl, M., Westfechtel, B. (eds.) WG 2004. LNCS, vol. 3353, pp. 332–343. Springer, Heidelberg (2004), http://www.springerlink.com/content/fepu2a3hd195ffjg/
Biedl, T.C., Bose, P., Demaine, E.D., Lubiw, A.: Efficient algorithms for Petersen’s matching theorem. J. Algorithms 38(1), 110 (2001), doi:10.1006/jagm.2000.1132
Brandes, U., Schlieper, B.: Angle and distance constraints on tree drawings. In: Kaufmann, M., Wagner, D. (eds.) GD 2006. LNCS, vol. 4372, pp. 54–65. Springer, Heidelberg (2007), doi:10.1007/978-3-540-70904-6_7
Brandes, U., Shubina, G., Tamassia, R.: Improving angular resolution in visualizations of geographic networks. In: Data Visualization 2000. Proc. 2nd Eurographics/IEEE TCVG Symp. Visualization (VisSym 2000), pp. 23–32. Springer, Heidelberg (2000)
Brandes, U., Wagner, D.: Using graph layout to visualize train interconnection data. J. Graph Algorithms Appl. 4(3), 135–155 (2000)
Cheng, C.C., Duncan, C.A., Goodrich, M.T., Kobourov, S.G.: Drawing planar graphs with circular arcs. Discrete Comput. Geom. 25(3), 405–418 (2001), doi:10.1007/s004540010080
Cole, R., Ost, K., Schirra, S.: Edge-coloring bipartite multigraphs in O(E log D) time. Combinatorica 21(1), 5–12 (2001), doi:10.1007/s004930170002
di Battista, G., Vismara, L.: Angles of planar triangular graphs. SIAM J. Discrete Math. 9(3), 349 (1996), doi:10.1137/S0895480194264010
Duncan, C.A., Eppstein, D., Goodrich, M.T., Kobourov, S.G., Nöllenburg, M.: Lombardi Drawings of Graphs. (September 2010) ArXiv e-prints, arXiv:1009.0579
Duncan, C.A., Eppstein, D., Goodrich, M.T., Kobourov, S.G., Nöllenburg, M.: Drawing trees with perfect angular resolution and polynomial area. In: Proc. 18th Int. Symp. on Graph Drawing (GD 2010), Springer, Heidelberg (2010)
Efrat, A., Erten, C., Kobourov, S.G.: Fixed-location circular arc drawing of planar graphs. J. Graph Algorithms Appl. 11(1), 145–164 (2007), http://jgaa.info/accepted/2007/EfratErtenKobourov2007.11.1.pdf
Finkel, B., Tamassia, R.: Curvilinear graph drawing using the force-directed method. In: Pach, J. (ed.) GD 2004. LNCS, vol. 3383, pp. 448–453. Springer, Heidelberg (2005), doi:10.1007/978-3-540-31843-9_46
Gabow, H.N.: Using Euler partitions to edge color bipartite multigraphs. Int. J. Parallel Programming 5(4), 345–355 (1976), doi:10.1007/BF00998632
Gansner, E.R., Koren, Y.: Improved circular layouts. In: Kaufmann, M., Wagner, D. (eds.) GD 2006. LNCS, vol. 4372, pp. 386–398. Springer, Heidelberg (2007), doi:10.1007/978-3-540-70904-6_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
Halin, R.: Über simpliziale Zerfällungen beliebiger (endlicher oder unendlicher) Graphen. Math. Ann. 156(3), 216–225 (1964), doi:10.1007/BF01363288
Holm, J., de Lichtenberg, K., Thorup, M.: Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity. J. ACM 48(4), 723–760 (2001), doi:10.1145/502090.502095
Kant, G.: Drawing planar graphs using the canonical ordering. Algorithmica 16, 4–32 (1996), doi:10.1007/BF02086606
Kőnig, D.: Gráfok és mátrixok. Matematikai és Fizikai Lapok 38, 116–119 (1931)
Lick, D.R., White, A.T.: K-degenerate graphs. Canad. J. Math. 22, 1082–1096 (1970), http://www.smc.math.ca/cjm/v22/p1082
Lombardi, M., Hobbs, R.: Mark Lombardi: Global Networks. Independent Curators (2003)
Malitz, S., Papakostas, A.: On the angular resolution of planar graphs. SIAM J. Discrete Math. 7(2), 172–183 (1994), doi:10.1137/S0895480193242931
Morgan, F.: Soap bubbles in ℝ2 and in surfaces. Pacific J. Math. 165(2), 347–361 (1994), http://projecteuclid.org/euclid.pjm/1102621620
Mulder, H.M.: Julius Petersen’s theory of regular graphs. Discrete Mathematics 100(1-3), 157–175 (1992), doi:10.1016/0012-365X(92)90639-W
Petersen, J.: Die Theorie der regulären Graphs. Acta Math. 15(1), 193–220 (1891), doi:10.1007/BF02392606
Schrijver, A.: Bipartite edge coloring in O(Δm) time. SIAM J. Comput. 28(3), 841–846 (1999), doi:10.1137/S0097539796299266
Six, J.M., Tollis, I.G.: A framework for circular drawings of networks. In: Kratochvíl, J. (ed.) GD 1999. LNCS, vol. 1731, pp. 107–116. Springer, Heidelberg (1999)
Thorup, M.: Near-optimal fully-dynamic graph connectivity. In: Proc. 32nd ACM Symp. Theory of Computing (STOC 2000), pp. 343–350 (2000), doi:10.1145/335305.335345
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2011 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Duncan, C.A., Eppstein, D., Goodrich, M.T., Kobourov, S.G., Nöllenburg, M. (2011). Lombardi Drawings of Graphs. In: Brandes, U., Cornelsen, S. (eds) Graph Drawing. GD 2010. Lecture Notes in Computer Science, vol 6502. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-18469-7_18
Download citation
DOI: https://doi.org/10.1007/978-3-642-18469-7_18
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-18468-0
Online ISBN: 978-3-642-18469-7
eBook Packages: Computer ScienceComputer Science (R0)