  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 $\widetilde{O}(n \log(R/\varepsilon))$ expected run-time to
produce a solution that is $\varepsilon$ close to a true representation, where
$R$ is the ratio between the maximum and minimum circle radius in the true
representation.
