Balanced circle packings for planar graphs

DOI10.1007/978-3-662-45803-7_11MaRDI QIDQ2936919zbMATH OpenOpenAlexFDO

Authors Md. Jawaherul Alam, David Eppstein, Stephen G. Kobourov, Sergey Pupyrev, Michael T. Goodrich

Publication date 7 January 2015

Published in Progress in Pattern Recognition, Image Analysis, Computer Vision, and Applications (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1408.4902

zbMATH Keywords

circle-contact representations for planar graphs

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Graph representations (geometric and intersection representations, etc.) (05C62)

Abstract: We study balanced circle packings and circle-contact representations for planar graphs, where the ratio of the largest circle's diameter to the smallest circle's diameter is polynomial in the number of circles. We provide a number of positive and negative results for the existence of such balanced configurations.

Recommendations

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

Cited in

(5)

• Low Ply Drawings of Trees
• Contact Graphs of Circular Arcs
• Parabolic rectangle packings
• B0-VPG Representation of AT-free Outerplanar Graphs
• StreamTable: an area proportional visualization for tables with flowing streams

This page was built for publication: Balanced circle packings for planar graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2936919)