Computing Circle Packing Representations of Planar Graphs

Abstract

The Circle Packing Theorem states that every planar graph can be represented as the tangency graph of a family of internally-disjoint circles. A well-known generalization is the Primal-Dual Circle Packing Theorem for 3-connected planar graphs. The existence of these representations has widespread applications in theoretical computer science and mathematics; however, the algorithmic aspect has received relatively little attention. In this work, we present an algorithm based on convex optimization for computing a primal-dual circle packing representation of maximal planar graphs, i.e. triangulations. This in turn gives an algorithm for computing a circle packing representation of any planar graph. Both take $\tilde{O}(n\log (R/\epsilon ))$ expected run-time to produce a solution that is $\epsilon$ close to a true representation, where $R$ is the ratio between the maximum and minimum circle radius in the true representation.

arXiv comment19 pages, 10 figures. SODA 2020

References in corpus (5)

• A nearly-mlogn time solver for SDD linear systems
• Convex Polytopes: Extremal Constructions and f-Vector Shapes
• A Simple Proof of the Existence of a Planar Separator
• The Galois Complexity of Graph Drawing: Why Numerical Solutions are Ubiquitous for Force-Directed, Spectral, and Circle Packing Drawings
• Strongly Monotone Drawings of Planar Graphs