Planar Lombardi Drawings of Outerpaths

Löffler, Maarten and Nöllenburg, Martin (2013) Planar Lombardi Drawings of Outerpaths. In: 20th International Symposium, GD 2012, September 19-21, 2012, Redmond, WA, USA , pp. 561-562 (Official URL: http://link.springer.com/chapter/10.1007/978-3-642-36763-2_53).

Full text not available from this repository.

Abstract

Introduction A Lombardi drawing of a graph is a drawingwhere edges are represented by circular arcs that meet at each vertex v with perfect angular resolution 360°/deg(v) [3]. It is known that Lombardi drawings do not always exist, and in particular, that planar Lombardi drawings of planar graphs do not always exist [1], even when the embedding is not fixed. Existence of planar Lombardi drawings is known for restricted classes of graphs, such as subcubic planar graphs [4], trees [2], Halin graphs and some very symmetric planar graphs [3]. On the other hand, all 2-degenerate graphs, including all outerplanar graphs, have Lombardi drawings, but not necessarily planar ones [3]. One question that was left open is whether outerplanar graphs always have planar Lombardi drawings or not. In this note, we report that the answer is “yes” for a more restricted subclass: the outerpaths, i.e., outerplanar graphs whose weak dual is a path. We sketch an algorithm that produces an outerplanar Lombardi drawing of any outerpath, in linear time.

Item Type:Conference Poster
Additional Information:10.1007/978-3-642-36763-2_53
Classifications:P Styles > P.120 Circular
ID Code:1346

Repository Staff Only: item control page

References

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 and Applications 16(1), 85–108 (2012)

Eppstein, D.: Planar Lombardi Drawings for Subcubic Graphs. In: Didimo, W., Patrignani, M. (eds.) GD 2012. LNCS, vol. 7704, pp. 126–137. Springer, Heidelberg (2013) To appear arXiv:1206.6142