𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Revisiting decomposition analysis of geometric constraint graphs

✍ Scribed by R. Joan-Arinyo; A. Soto-Riera; S. Vila-Marta; J. Vilaplana-Pastó

Publisher
Elsevier Science
Year
2004
Tongue
English
Weight
651 KB
Volume
36
Category
Article
ISSN
0010-4485

No coin nor oath required. For personal study only.

✦ Synopsis

Geometric problems defined by constraints can be represented by geometric constraint graphs whose nodes are geometric elements and whose arcs represent geometric constraints. Reduction and decomposition are techniques commonly used to analyze geometric constraint graphs in geometric constraint solving.

In this paper we first introduce the concept of deficit of a constraint graph. Then we give a new formalization of the decomposition algorithm due to Owen. This new formalization is based on preserving the deficit rather than on computing triconnected components of the graph and is simpler. Finally we apply tree decompositions to prove that the class of problems solved by the formalizations studied here and other formalizations reported in the literature is the same.

📜 SIMILAR VOLUMES

Decomposition of bipartite graphs under
Decomposition of bipartite graphs under degree constraints
✍ H. J. Broersma; R. J. Faudree; J. Den Van Heuvel; H. J. Veldman 📂 Article 📅 1993 🏛 John Wiley and Sons 🌐 English ⚖ 339 KB

## Abstract Let __G__ = __(A, B; E)__ be a bipartite graph. Let __e__~1~, __e__~2~ be nonnegative integers, and __f__~1~, __f__~2~ nonnegative integer‐valued functions on __V(G)__ such that __e__~__i__~ ≦ |__E__| ≦ __e__~1~ + __e__~2~ and __f~i~(v)__ ≦ __d(v)__ ≦ __f__~1~__(v)__ + __f__~2~__(v)__ f

On decomposition of triangle-free graphs
On decomposition of triangle-free graphs under degree constraints
✍ Kaneko, Atsushi 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 80 KB 👁 2 views

We prove that if s and t are positive integers and if G is a triangle-free graph with minimum degree s + t, then the vertex set of G has a decomposition into two sets which induce subgraphs of minimum degree at least s and t, respectively.