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 , pp. 126-137(Official URL: http://link.springer.com/chapter/10.1007/978-3-642...).

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
Divisions: UNSPECIFIED
Depositing User: Administration GDEA
Date Deposited: 21 Nov 2013 13:45
Last Modified: 21 Nov 2013 13:45
URI: http://gdea.informatik.uni-koeln.de/id/eprint/1303

Actions (login required)

View Item View Item