DIRECTED RECTANGLE-VISIBILITY GRAPHS HAVE UNBOUNDED DIMENSION

Visibility representations of graphs map vertices to sets in Euclidean space and express edges as visibility relations between these sets. O ne 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 betw een the rectangles. Two rectangles are only considered to be visible t o one another if there is a nonzero width horizontal or vertical 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 direct ions, which yields a directed acyclic graph. A directed acyclic graph G has dimension d if d is the minimum integer such that the vertices o f G can be ordered by d linear orderings, <(l),..., <(d), and for vert ices u and v there is a directed path from u to v if and only if u <(i ) v for all 1 less than or equal to i less than or equal to d. In this note we show that the dimension of the class of directed rectangle-vi sibility graphs is unbounded.