A polynomial time circle packing algorithm

DOI10.1016/0012-365X(93)90340-YzbMath0785.52006OpenAlexW2057382776WikidataQ125757310 ScholiaQ125757310MaRDI QIDQ686175

Bojan Mohar

Publication date: 11 April 1994

Published in: Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0012-365x(93)90340-y

zbMATH Keywords

geodesicspolynomial algorithmtime complexitydual graphcircle packing representation

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Packing and covering in (2) dimensions (aspects of discrete geometry) (52C15)

Related Items

A circle packing algorithm ⋮ A linearized circle packing algorithm ⋮ On intersection representations of co-planar graphs ⋮ Packing disks by flipping and flowing ⋮ Contact Representations of Planar Graphs: Extending a Partial Representation is Hard ⋮ Existence and hardness of conveyor belts ⋮ Pointed drawings of planar graphs ⋮ Extending Steinitz's theorem to upward star-shaped polyhedra and spherical polyhedra ⋮ A Möbius-invariant power diagram and its applications to soap bubbles and planar Lombardi drawing ⋮ Circle Packing: Experiments In Discrete Analytic Function Theory ⋮ The partial visibility representation extension problem ⋮ Conformal mapping in linear time ⋮ Variational principles for circle patterns and Koebe’s theorem ⋮ Convex representations of maps on the torus and other flat surfaces

Cites Work

• Unnamed Item
• Unnamed Item
• A variational principle for circle packings.
• A Note on Planar Graphs and Circle Orders
• Empilements de cercles: Convergence d’une méthode de point fixe
• ON CONVEX POLYHEDRA IN LOBAČEVSKIĬ SPACES
• ON CONVEX POLYHEDRA OF FINITE VOLUME IN LOBAČEVSKIĬ SPACE
• How to Draw a Graph