A CHARACTERIZATION OF INTERSECTION GRAPHS OF THE MAXIMAL RECTANGLES OF A POLYAMINO

Authors
MAIRE F
Citation
F. Maire, A CHARACTERIZATION OF INTERSECTION GRAPHS OF THE MAXIMAL RECTANGLES OF A POLYAMINO, Discrete mathematics, 120(1-3), 1993, pp. 211-214
Citations number
5
Categorie Soggetti
Mathematics, Pure",Mathematics
Journal title
Discrete mathematics → ACNP
ISSN journal
0012365X
Volume
120
Issue
1-3
Year of publication
1993
Pages
211 - 214
Database
ISI
SICI code
0012-365X(1993)120:1-3<211:ACOIGO>2.0.ZU;2-2
Abstract
The interior of an orthogonal polygon drawn on a regular grid of the p lane defines a set of cells (or squares) called a polyomino. We prove that the intersection graph of the maximal rectangles contained in a p olyomino is slightly triangulated or has a star cutset.