Planar Lombardi Drawings for Subcubic Graphs

Eppstein, David (2013) Planar Lombardi Drawings for Subcubic Graphs. In: 20th International Symposium, GD 2012, September 19-21, 2012, Redmond, WA, USA , pp. 126-137 (Official URL: http://link.springer.com/chapter/10.1007/978-3-642-36763-2_12).

Full text not available from this repository.

Abstract

We prove that every planar graph with maximum degree three has a planar drawing in which the edges are drawn as circular arcs that meet at equal angles around every vertex. Our construction is based on the Koebe–Andreev–Thurston circle packing theorem, and uses a novel type of Voronoi diagram for circle packings that is invariant under Möbius transformations, defined using three-dimensional hyperbolic geometry. We also use circle packing to construct planar Lombardi drawings of a special class of 4-regular planar graphs, the medial graphs of polyhedral graphs, and we show that not every 4-regular planar graph has a planar Lombardi drawing. We have implemented our algorithm for 3-connected planar cubic graphs.

Item Type:Conference Paper
Additional Information:10.1007/978-3-642-36763-2_12
Classifications:M Methods > M.600 Planar
M Methods > M.999 Others
P Styles > P.120 Circular
P Styles > P.540 Planar
ID Code:1303

Repository Staff Only: item control page

References

Bern, M., Eppstein, D.: Optimal Möbius Transformations for Information Visualization and Meshing. In: Dehne, F., Sack, J.-R., Tamassia, R. (eds.) WADS 2001. LNCS, vol. 2125, pp. 14–25. Springer, Heidelberg (2001)

Cannon, J.W., Floyd, W.J., Kenyon, R., Parry, W.R.: Hyperbolic geometry. In: Levy, S. (ed.) Flavors of Geometry. MSRI Publications, vol. 31, pp. 59–115. Cambridge Univ. Press, Cambridge (1997)

Chernobelskiy, R., Cunningham, K.I., 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 (2012)

Collins, C.R., Stephenson, K.: A circle packing algorithm. Comput. Geom. Th. Appl. 25(3), 233–256 (2003)

Di Battista, G., Tamassia, R.: Incremental planarity testing. In: 30th Symp. Foundations of Computer Science, pp. 436–441. IEEE (1989)

Di Battista, G., Tamassia, R.: On-Line Graph Algorithms with SPQR-Trees. In: Paterson, M. (ed.) ICALP 1990. LNCS, vol. 443, pp. 598–611. Springer, Heidelberg (1990)

Došlić, T.: On some structural properties of fullerene graphs. J. Math. Chem. 31(2), 187–195 (2002)

Duncan, C.A., Eppstein, D., Goodrich, M.T., Kobourov, S.G., Löffler, M.: Planar and Poly-arc Lombardi Drawings. In: van Kreveld, M., Speckmann, B. (eds.) GD 2011. LNCS, vol. 7034, pp. 308–319. Springer, Heidelberg (2012)

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)

Duncan, C.A., Eppstein, D., Goodrich, M.T., Kobourov, S.G., Nöllenburg, M.: Lombardi drawings of graphs. J. Graph. Algorithms & Appl. 16(1), 85–108 (2012)

Eppstein, D.: Quasiconvex programming. In: Goodman, J.E., Pach, J., Welzl, E. (eds.) Combinatorial and Computational Geometry. MSRI Publications, vol. 52, pp. 287–331. Cambridge Univ. Press, Cambridge (2005)

Eppstein, D.: The graphs of planar soap bubbles (2012), preprint arXiv:1207.3761

Eppstein, D., Dillencourt, M.B.: Uninscribable 4-regular polyhedron. Electronic Geometry Models, 2003.08.001 (2003), http://www.eg-models.de/2003.08.001/

Eppstein, D., Mumford, E.: Steinitz theorems for orthogonal polyhedra. In: 26th Symp. Comput. Geom., pp. 429–438. ACM (2010)

Grinberg, È.J.: Plane homogeneous graphs of degree three without Hamiltonian circuits. In: Latvian Math. Yearbook 4, pp. 51–58. Izdat. “Zinatne”, Riga (1968)

Gutwenger, C., Mutzel, P.: A Linear Time Implementation of SPQR-Trees. In: Marks, J. (ed.) GD 2000. LNCS, vol. 1984, pp. 77–90. Springer, Heidelberg (2001)

Hopcroft, J., Tarjan, R.: Dividing a graph into triconnected components. SIAM J. Comput. 2(3), 135–158 (1973)

Kimberling, C.: Triangle Centers and Central Triangles. Utilitas Math. (1998)

Löffler, M., Nöllenburg, M.: Planar Lombardi drawings of outerpaths (2012) (manuscript)

Mac Lane, S.: A structural characterization of planar combinatorial graphs. Duke Math. J. 3(3), 460–472 (1937)

Markström, K.: Extremal graphs for some problems on cycles in graphs. Congr. Numerantium 171, 179–192 (2004)

Mohar, B.: A polynomial time circle packing algorithm. Discrete Math. 117(1-3), 257–263 (1993)

Pootheri, S.K.: Decomposition characterizations of classes of 2-connected graphs. In: 39th Southeast Conf. ACM (2001)

Schwerdtfeger, H.: Geometry of Complex Numbers: Circle Geometry, Moebius Transformation, Non-Euclidean Geometry. Dover (1979)

Stephenson, K.: Introduction to Circle Packing: The Theory of Discrete Analytic Functions. Cambridge University Press (2005)

Tutte, W.T.: On Hamiltonian circuits. J. London Math. Soc. 21(2), 98–101 (1946)