Circle packings of maps in polynomial time
type: Item
instance of: scholarly article
title: Circle packings of maps in polynomial time
zbMATH Open document ID: 0891.52008
author: Bojan Mohar
published in: European Journal of Combinatorics
publication date: 1997-11-18T00:00:00Z
review text: 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\).
Mathematics Subject Classification ID: 52C15
Mathematics Subject Classification ID: 05C10
Mathematics Subject Classification ID: 57M15
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 1088575
zbMATH Keywords: polynomial time algorithm
zbMATH Keywords: circle packing
reviewed by: Eike Hertel
MaRDI profile type: Publication
full work available at URL: eujc.1996.0135
OpenAlex ID: W2003689196
Wikidata QID: Q126100788
DOI: 10.1006/EUJC.1996.0135
description: scientific article; zbMATH DE number 1088575