𝔖 Bobbio Scriptorium
✦   LIBER   ✦

A characterization of intersection graphs of the maximal rectangles of a polyomino

✍ Scribed by Frédéric Maire

Publisher
Elsevier Science
Year
1993
Tongue
English
Weight
213 KB
Volume
120
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

✦ Synopsis

The interior of an orthogonal polygon drawn on a regular grid of the plane defines a set of cells (or squares) called a polyomino.

We prove that the intersection graph of the maximal rectangles contained in a polyomino is slightly triangulated or has a star cutset.

📜 SIMILAR VOLUMES

A Characterization and the Intersection
A Characterization and the Intersection of the Maximal Compatible Extensions of a Partial Order
✍ Szilvia Szilágyi 📂 Article 📅 2008 🏛 Springer Netherlands 🌐 English ⚖ 364 KB

We present a characterization of the maximal compatible extensions of a given compatible partial order ≤ r on a unary algebra (A,f ). These extensions can be constructed by using the compatible linear extensions of ≤ r*, where (A*,f*) is the so called contracted quotient algebra of (A,f)

Intersection properties of graphs
Intersection properties of graphs
✍ Terry A. McKee 📂 Article 📅 1991 🏛 Elsevier Science 🌐 English ⚖ 550 KB

McKee, T.A., Intersection properties of graphs, Discrete Mathematics 89 (1991) 253-260. For each graph-theoretic property, we define a corresponding 'intersection property', motivated by the natural relationship of paths with interval graphs, and of trees with chordal graphs. We then develop a simp