A polynomial time circle packing algorithm
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.
- A Note on Planar Graphs and Circle Orders
- A variational principle for circle packings.
- Empilements de cercles: Convergence d’une méthode de point fixe
- How to Draw a Graph
- scientific article; zbMATH DE number 3759178 (Why is no real title available?)
- scientific article; zbMATH DE number 3027510 (Why is no real title available?)
- ON CONVEX POLYHEDRA IN LOBAČEVSKIĬ SPACES
- ON CONVEX POLYHEDRA OF FINITE VOLUME IN LOBAČEVSKIĬ SPACE
- A variational principle for circle packings.
- Convex representations of maps on the torus and other flat surfaces
- Circle packings of maps in polynomial time
- On intersection representations of co-planar graphs
- A circle packing algorithm
- Existence and hardness of conveyor belts
- A linearized circle packing algorithm
- PERM for solving circle packing problem
- Packing disks by flipping and flowing
- scientific article; zbMATH DE number 1629820 (Why is no real title available?)
- Balanced circle packings for planar graphs
- Contact representations of planar graphs: extending a partial representation is hard
- Variational principles for circle patterns and Koebe’s theorem
- Pointed drawings of planar graphs
- A Möbius-invariant power diagram and its applications to soap bubbles and planar Lombardi drawing
- Circle packings of maps —The Euclidean case
- Circle Packing: Experiments In Discrete Analytic Function Theory
- Conformal mapping in linear time
- Extending Steinitz's theorem to upward star-shaped polyhedra and spherical polyhedra
- On primal-dual circle representations
- VOROPACK-D: real-time disk packing algorithm using Voronoi diagram
This page was built for publication: A polynomial time circle packing algorithm
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q686175)
