A polynomial time circle packing algorithm (Q686175): Difference between revisions

A map on a surface \(S\) is a pair \((G,S)\) with \(G\) a graph which is 2-cell embedded in \(S\). A circle packing is a set of geodesic circles, with disjoint interiors, in a Riemannian surface \(S'\) of constant curvature. Connecting the midpoints of the circles with the touching points (with other circles or the same circle), one gets a graph on \(S'\). If such a graph is a map, isomorphic to the map \(M=(G,S)\), then one has a circle packing representation of \(M\). Simultaneous distinct circle packing representations of a map and its dual map, with any two dual edges crossing each other at the right angle in the corresponding circle touching point, are called primal-dual circle packing representations. A theorem of Koebe, Andreev, and Thurston says that if \(M\) is a triangulation then it admits a circle packing representation. The present paper contains extensions and improvements. The necessary and sufficient condition for a map to have a primal-dual circle packing representation is that its universal cover graph is 3-connected. Given a map \(M\) and a rational \(\varepsilon>0\), then one can find an \(\varepsilon\)- approximation for the primal-dual circle packing representation of \(M\) in polynomial time. In particular, there is a polynomial time algorithm producing simultaneous geodesic line convex drawings of a given map and its dual in a surface of constant curvature, so that only edges dual to each other cross.