95-07 Directed Rectangle-Visibility Graphs have Unbounded Dimension

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