Lombardi Drawings of Graphs

Duncan, Christian A. and Eppstein, David and Goodrich, Michael T. and Kobourov, Stephen G. and Nöllenburg, Martin (2011) Lombardi Drawings of Graphs. In: Graph Drawing 18th International Symposium, GD 2010, September 21-24, 2010, Konstanz, Germany , pp. 195-207 (Official URL: http://dx.doi.org/10.1007/978-3-642-18469-7_18).

Full text not available from this repository.

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.

Item Type:Conference Paper
Additional Information:10.1007/978-3-642-18469-7_18
Classifications:P Styles > P.999 Others
ID Code:1206

Repository Staff Only: item control page

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),

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),

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),

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),

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