Planar and Poly-arc Lombardi Drawings

Duncan, Christian A. and Eppstein, David and Goodrich, Michael T. and Kobourov, Stephen G. and Löffler, Maarten (2012) Planar and Poly-arc Lombardi Drawings. In: Graph Drawing 19th International Symposium, GD 2011, September 21-23, 2011, Eindhoven, The Netherlands , pp. 308-319 (Official URL: http://dx.doi.org/ 10.1007/978-3-642-25878-7_30).

Full text not available from this repository.

Abstract

In Lombardi drawings of graphs, edges are represented as circular arcs, and the edges incident on vertices have perfect angular resolution. However, not every graph has a Lombardi drawing, and not every planar graph has a planar Lombardi drawing. We introduce k-Lombardi drawings, in which each edge may be drawn with k circular arcs, noting that every graph has a smooth 2-Lombardi drawing. We show that every planar graph has a smooth planar 3-Lombardi drawing and further investigate topics connecting planarity and Lombardi drawings.

Item Type:Conference Paper
Additional Information:10.1007/978-3-642-25878-7_30
Classifications:M Methods > M.600 Planar
P Styles > P.300 Curved
ID Code:1265

Repository Staff Only: item control page

References

Aichholzer, O., Aigner, W., Aurenhammer, F., Dobiáošvá, K.Č., Jüttler, B.: Arc triangulations. In: Proc. 26th Eur. Worksh. Comp. Geometry (EuroCG 2010), Dortmund, Germany, pp. 17–20 (2010)

Andrade Jr., J.S., Herrmann, H.J., Andrade, R.F.S., da Silva, L.R.: Apollonian networks: Simultaneously scale-free, small world, Euclidean, space filling, and with matching graphs. Physics Review Letters 94, 018702 (2005); arXiv:cond-mat/0406295

Brandes, U., Wagner, D.: Using graph layout to visualize train interconnection data. J. Graph Algorithms Appl. 4(3), 135–155 (2000), http://jgaa.info/accepted/00/BrandesWagner00.4.3.pdf

Cheng, C.C., Duncan, C.A., Goodrich, M.T., Kobourov, S.G.: Drawing planar graphs with circular arcs. Discrete Comput. Geom. 25(3), 405 (2001), doi:10.1007/s004540010080

Chernobelskiy, R., Cunningham, K., Goodrich, M.T., Kobourov, S.G., Trott, L.: Force-directed Lombardi-style graph drawing. In: van Kreveld, M., Speckmann, B. (eds.) GD 2011. LNCS, vol. 7034, pp. 320–331. Springer, Heidelberg (2011)

Di Battista, G., Vismara, L.: Angles of planar triangular graphs. SIAM J. Discrete Math. 9(3), 349–359 (1996), doi:10.1137/S0895480194264010

Dickerson, M., Eppstein, D., Goodrich, M.T., Meng, J.Y.: Confluent drawings: Visualizing non-planar diagrams in a planar way. J. Graph Algorithms Appl. 9(1), 31–52 (2005), http://jgaa.info/accepted/2005/Dickerson+2005.9.1.pdf

Duncan, C.A., Eppstein, D., Goodrich, M.T., Kobourov, S.G., Löffler, M.: Planar and poly-arc Lombardi drawings. ArXiv e-prints abs/1109.0345, arXiv:1109.0345 (September 2011)

Duncan, C.A., Eppstein, D., Goodrich, M.T., Kobourov, S.G., Nöllenburg, M.: Drawing Trees With Perfect Angular Resolution and Polynomial Area. In: Brandes, U., Cornelsen, S. (eds.) GD 2010. LNCS, vol. 6502, pp. 183–194. Springer, Heidelberg (2011), doi:10.1007/978-3-642-18469-7 17; arXiv:1009.0581

Duncan, C.A., Eppstein, D., Goodrich, M.T., Kobourov, S.G., Nöllenburg, M.: Lombardi Drawings of Graphs. In: Brandes, U., Cornelsen, S. (eds.) GD 2010. LNCS, vol. 6502, pp. 195–207. Springer, Heidelberg (2011), doi:10.1007/978-3-642-18469-7 18; arXiv:1009.0579

Eppstein, D., Goodrich, M.T., Meng, J.Y.: Delta Confluent Drawings. In: Healy, P., Nikolov, N.S. (eds.) GD 2005. LNCS, vol. 3843, pp. 165–176. Springer, Heidelberg (2006), doi:10.1007/11618058 16; arXiv:cs/0510024v1

Eppstein, D., Goodrich, M.T., Meng, J.Y.: Confluent layered drawings. Algorithmica 47(4), 439–452 (2007), doi:10.1007/s00453-006-0159-8

Eppstein, D., Löffler, M., Mumford, E., Nöllenburg, M.: Optimal 3D Angular Resolution for Low-Degree Graphs. In: Brandes, U., Cornelsen, S. (eds.) GD 2010. LNCS, vol. 6502, pp. 208–219. Springer, Heidelberg (2011), doi:10.1007/978-3-642-18469-7 19; arXiv:1009.0045

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

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

Goodrich, M.T., Wagner, C.G.: A framework for drawing planar graphs with curves and polylines. Journal of Algorithms 37(2), 399–421 (2000), doi:10.1006/jagm.2000.1115

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

Hirsch, M., Meijer, H., Rappaport, D.: Biclique Edge Cover Graphs and Confluent Drawings. In: Kaufmann, M., Wagner, D. (eds.) GD 2006. LNCS, vol. 4372, pp. 405–416. Springer, Heidelberg (2007), doi:10.1007/978-3-540-70904-6 39

Holten, D., van Wijk, J.J.: Force-directed edge bundling for graph visualization. Computer Graphics Forum 28, 983–990 (2009), doi:10.1111/j.1467-8659.2009.01450.x

Kant, G.: Drawing planar graphs using the canonical ordering. Algorithmica 16, 4–32 (1996), doi:10.1007/BF02086606

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

Matsakis, N.: Transforming a random graph drawing into a Lombardi drawing. ArXiv ePrints abs/1012.2202, arXiv:1012.2202 (December 2010)