Recognizing and Coloring Rectangle Visibility Graphs

A rectangle-visibility graph is one whose vertices can each be represented by a closed rectangle in the plane with sides parallel to the axes, having pairwise disjoint interiors, with two vertices adjacent in the graph if and only if the corresponding rectangles are vertically or horizontally visible. Two rectangles are vertically (respectively, horizontally) visible when there is a nondegenerate rectangle R such that R intersects only these two rectangles and the horizontal (resp., vertical) sides of R are subsets of these two rectangles.

Question: What is the maximum chromatic number of rectangle-visibility graphs?

These graphs have thickness at most two since their edges can be divided into vertical and horizontal visibilities, each forming a planar graph. Hence this question is related to Ringel's Earth-Moon coloring problem.

The one-dimensional analogue, bar-visibility graphs, has been characterized [TT,W]. Some properties of rectangle-visibility graphs are known, for example, edge-density properties and representations of complete and of complete bipartite graphs [HSV,DH]. It is known that a thickness-two graph that is the union of two bar-visibility graphs need not be a rectangle-visibility graph, though the converse is true.

Question: Is it NP-complete to recognize rectangle-visibility graphs?

It is NP-complete to recognize graphs of thickness two [M]. The problem is known to lie in NP (Alice Dean, personal communication).

References:

[DH] A. Dean and J. P. Hutchinson, Rectangle-visibility representations of bipartite graphs, Extended Abstract, Lecture Notes in Computer Science (Proc. DIMACS Workshop Graph Drawing, 1994), R. Tamassia and I. G. Tollis, eds., vol. 894, Springer-Verlag, 1995, 159-166.

[HSV] J. P. Hutchinson, T. Shermer, and A. Vince, On Representations of some Thickness-two Graphs, submitted.

[M] A. Mansfield, Determining the thickness of graphs is NP-hard, Math. Proc. Cambridge Phil. Soc. 93 (1983), 9-23.

[TT] R. Tamassia and I. G. Tollis, A unified approach to visibility representations of planar graphs, Disc. and Comp. Geom. 1 (1986), 321-341.

[W] S. K. Wismath, Characterizing bar line-of-sight graphs, Proc. 1st Symp. Comp. Geom., ACM (1985), 147-152.

Submitted by: Joan P. Hutchinson, Department of Mathematics and Computer Science, Macalester College, St. Paul MN, USA 55105

Send comments to dan.archdeacon@uvm.edu and to hutchinson@macalstr.edu

August, 1995