Circle packings of maps in polynomial time (Q1372615)

A map \(M\) is a pair \((G,\Sigma)\) where \(G\) is a connected graph embedded in a closed surface \(\Sigma\). A circle packing (representation) of \(M\) is a set of (geodesic) circles (disks) in a Riemannian surface \(\Sigma'\) of constant curvature which is homeomorphic to \(\Sigma\), one circle for each vertex of \(G\) with the following conditions: for each edge \(uv\) of \(G\), the circle corresponding to \(u\) and \(v\) touch, and by using the centres of each circle \(D\) as a vertex \(v_D\) and joining \(v_D\) by geodesics with all points on the boundary of \(D\) where the other circles touch \(D\), one obtains a map on \(\Sigma'\) which is isomorphic to \(M\). It is well known that a triangulation \(M\) admits a circle packing representation. The author generalizes this result to the most general maps (maps with 3-connected universal cover) which admit so called primal-dual circle packing representations. Further, he gives a polynomial time algorithm that finds an \(\varepsilon\)-approximation for the radii and the coordinates of the centres for such a circle packing representation of a map \(M\).