✦ LIBER ✦

A polynomial time circle packing algorithm

✍ Scribed by Bojan Mohar

Publisher: Elsevier Science
Year: 1993
Tongue: English
Weight: 428 KB
Volume: 117
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(93)90340-y

No coin nor oath required. For personal study only.

✦ Synopsis

Mohar, B., A polynomial time circle packing algorithm, Discrete Mathematics 117 (1993) 2577263.

The Andreev-Koebe-Thurston circle packing theorem is generalized and improved in two ways. Simultaneous circle packing representations of the map and its dual map are obtained such that any two edges dual to each other cross at the right angle. The necessary and sufficient condition for a map to have such a primal-dual circle packing representation is that its universal cover graph is 3-connected.

A polynomial time algorithm is obtained that given such a map M and a rational number E > 0 finds an a-approximation for the primal-dual circle packing representation of M. In particular, there is a polynomial time algorithm that produces simultaneous geodesic line convex drawings of a given map and its dual in a surface with constant curvature, so that only edges dual to each other cross.

📜 SIMILAR VOLUMES

Circle Packings of Maps in Polynomial Ti

Circle Packings of Maps in Polynomial Time

✍ Bojan Mohar 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 275 KB

The Andreev-Koebe-Thurston circle packing theorem is generalized and improved in two ways. First, we obtain simultaneous circle packings of the map and its dual map so that, in the corresponding straight-line representations of the map and the dual, any two edges dual to each other are perpendicular

A polynomial time algorithm recognizing

A polynomial time algorithm recognizing link trees

✍ Peter Bugata; Attila Nagy; Roman Vávra 📂 Article 📅 1995 🏛 John Wiley and Sons 🌐 English ⚖ 672 KB

The link of a vertex u of a graph G is the subgraph induced by all vertices adjacent to u . If all the links of G are isomorphic to a finite graph L, then G is called a realization of L, and L is called a link graph. At the Smolenice symposium of 1963, Zykov posed the problem of recognizing iink gr

A 5/4 Linear Time Bin Packing Algorithm

✍ József Békési; Gábor Galambos; Hans Kellerer 📂 Article 📅 2000 🏛 Elsevier Science 🌐 English ⚖ 195 KB

In 1985, Martel published a linear time algorithm with a 4 3 asymptotic worst-case ratio for the one-dimensional bin packing problem. The algorithm is based on a linear time classification of the sizes of the items, and thereafter according to the number of elements in certain subclasses pairing the

A Polynomial Time Algorithm for Unidimen

A Polynomial Time Algorithm for Unidimensional Unfolding Representations

✍ J.P. Doignon; J.C. Falmagne 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 629 KB

A Polynomial-Time Parsing Algorithm forK

A Polynomial-Time Parsing Algorithm forK-Depth Languages

✍ Alessandra Cherubini; Pierluigi San Pietro 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 736 KB

K-depth grammars extend context-free grammars allowing k 1 rewriting points for a single non-terminal at every step of a derivation. The family of languages generated by k-depth grammars is a proper extension of the family of context-free languages, while retaining many context-free properties, such

A Polynomial-time Algorithm for the Bist

A Polynomial-time Algorithm for the Bistable Roommates Problem

✍ Jay Sethuraman; Chung-Piaw Teo 📂 Article 📅 2001 🏛 Elsevier Science 🌐 English ⚖ 127 KB

In a recent paper, Weems introduced the bistable matching problem, and asked if a polynomial-time algorithm exists to decide the feasibility of the bistable roommates problem. We resolve this question in the affirmative using linear programming. In addition, we show that several (old and new) result