A polynomial time circle packing algorithm

DOI10.1016/0012-365X(93)90340-YMaRDI QIDQ686175zbMATH OpenOpenAlexWikidataFDO

Authors 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)

Recommendations

• Circle packings of maps in polynomial time
• Existence and uniqueness of packings with specified combinatorics
• Circle packings of maps —The Euclidean case
• A variational principle for circle packings.
• A circle packing algorithm

Cites work

• scientific article; zbMATH DE number 3759178 (Why is no real title available?)
• scientific article; zbMATH DE number 3027510 (Why is no real title available?)
• 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
• ON CONVEX POLYHEDRA IN LOBAČEVSKIĬ SPACES
• ON CONVEX POLYHEDRA OF FINITE VOLUME IN LOBAČEVSKIĬ SPACE

Cited in

(19)

• A variational principle for circle packings.
• Existence and hardness of conveyor belts
• A circle packing algorithm
• A linearized circle packing algorithm
• Packing disks by flipping and flowing
• Conformal mapping in linear time
• Balanced circle packings for planar graphs
• A Möbius-invariant power diagram and its applications to soap bubbles and planar Lombardi drawing
• Contact representations of planar graphs: extending a partial representation is hard
• Convex representations of maps on the torus and other flat surfaces
• Circle Packing: Experiments In Discrete Analytic Function Theory
• scientific article; zbMATH DE number 1629820 (Why is no real title available?)
• Circle packings of maps —The Euclidean case
• Variational principles for circle patterns and Koebe’s theorem
• On intersection representations of co-planar graphs
• On primal-dual circle representations
• Extending Steinitz's theorem to upward star-shaped polyhedra and spherical polyhedra
• Pointed drawings of planar graphs
• PERM for solving circle packing problem

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)