Information Technology Reference
In-Depth Information
Minimum Representations
of Rectangle Visibility Graphs
John S. Caughman
1
, Charles L. Dunn
2
,JoshuaD.Laison
3
,
Nancy Ann Neudauer
4
, and Colin L. Starr
3
1
Department of Mathematics and Statistics, Portland State University,
Box 751, Portland, OR 97202, USA
2
Department of Mathematics, Linfield College, 900 SE Baker Street,
McMinnville, OR 97128, USA
3
Department of Mathematics, Willamette University, Salem, OR 97301, USA
4
Department of Mathematics & Computer Science, Pacific University,
Forest Grove, OR 97116, USA
Let
S
be a set of nonintersecting open rectangles in the plane with horizontal
and vertical sides. Two rectangles
R
1
and
R
2
are
visible
if there exists a
line
of sight
between them, a horizontal or vertical line segment that intersects
both
R
1
and
R
2
but no other object in
S
. We construct a graph
G
with a
vertex for each rectangle in
S
, and an edge between two vertices if and only
if their corresponding rectangles are visible. Note that we require rectangles to
have positive width and height, but two rectangles may share a part of their
boundary, so the distance between two rectangles may be 0. For a given graph
G
, if such a representation of
G
with rectangles exists then
G
is a
rectangle
visibility graph
(
RVG
)and
S
is a
rectangle visibility representation
of
G
[1].
Suppose the corners of the rectangles in
S
have integer coordinates. For a
given RVG
G
, we ask how small its rectangle visibility representation can be.
We think of the size of a rectangle visibility representation as the area of the
smallest axis-parallel rectangle that encloses it (the
area
of
S
), or as the length
of the shorter side of this rectangle (the
height
of
S
). Kant, Liotta, Tamassia,
and Tollis [2] found the area of a rectangle visibility representation of a tree
up to a multiplicative constant. In this work, we find the height of a rectangle
visibility representation of a tree within an additive constant of 1. We also ask
for the RVG with
n
vertices and largest area (i.e. the maximum over all graphs
G
on
n
vertices of the minimum area of any rectangle visibility representation
of
G
). We begin answering this question for small values of
n
. Specifically, we
prove the following theorems.
Theorem 1.
Among graphs with n vertices,
1
≤
n
≤
6
, the empty graphs E
n
have largest area, n
2
.
Theorem 2.
Among graphs with n vertices, n
≥
7
, the empty graphs E
n
do not
have largest area.
To prove Theorem 2, we show first that the graphs
K
7
and
K
8
must be
enclosed by axis-parallel rectangles of dimensions at least 7
×
8and10
×
10, and
