## DIMACS TR: 95-07

## Directed Rectangle-Visibility Graphs have Unbounded Dimension

### Author: Kathleen Romanik

**
ABSTRACT
**

Visibility representations of graphs map vertices to sets in
Euclidean space and express edges as visibility relations between
these sets. One visibility representation in the plane that has been
studied is one in which the vertices of the graph map to closed
isothetic rectangles and the edges are expressed by horizontal or
vertical visibility between the rectangles. Two rectangles are only
considered to be visible to one another if there is a non-zero width
horizontal orvertical band of sight between them. A graph that can be
represented in this way is called a rectangle-visibility graph.
A rectangle-visibility graph can be directed by directing all edges
towards the positive x and y directions, which yields a directed
acyclic graph. A directed acyclic graph G has dimension d if d is the
minimum integer such that the vertices of G can be ordered by d linear
orderings, <_1, ..., <_d, and for vertices u and v there is a directed
path from u to v if and only if u <_i v for all 1 <= i <= d. In this
note we show that the dimension of the class of directed
rectangle-visibility graphs is unbounded.

Paper available at:
ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1995/95-07.ps.gz

DIMACS Home Page