Stefan Felsner and Günter Rote:

On primal-dual circle representations

1. In: Abstracts of the 34th European Workshop on Computational Geometry (EuroCG 2018), Berlin, March 2018, pp. 72:1–72:6.  →BibTeX (preliminary version)
2. In: Proceedings of the 2nd Symposium on Simplicity in Algorithms (SOSA 2019), San Diego, January 2019, Editors: Jeremy Fineman and Michael Mitzenmacher, OpenAccess Series in Informatics (OASIcs), Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2019, Vol. 69, pp. 8:1–8:18. doi:10.4230/OASIcs.SOSA.2019.8  →BibTeX

Abstract

The Koebe–Andreev–Thurston Circle Packing Theorem states that every triangulated planar graph has a circle-contact representation. The theorem has been generalized in various ways. The arguably most prominent generalization assures the existence of a primal-dual circle representation for every 3-connected planar graph. The aim of this note is to give a streamlined and self-contained elementary proof of this result.