Rectangle-visibility Layouts of Unions and Products of Trees
Alice M. Dean, Joan P. Hutchinson · Journal of Graph Algorithms and Applications · 1998
The paper considers representations of unions and products of trees as rectangle-visibility graphs (abbreviated RVGs), i.e., graphs whose vertices are rectangles in the plane, with adjacency determined by horizontal and vertical visibility. Our main results are that the union of any tree (or forest) with a depth-1 tree is an RVG, and that the union of two depth-2 trees and the union of a depth-3 tree with a matching are subgraphs of RVGs. We also show that the cartesian product of two forests is an RVG. Communicated by J. S. B. Mitchell: submitted January 1998; revised September 1998. A. Dean and J. Hutchinson, RVG Layouts, JGAA, 2(8) 1-21 (1998) 2 1 Introduction In this paper we study aspects of the question of how to represent a graph in the plane as a rectangle-visibility graph (RVG for short). In such a representation the vertices are drawn as rectangles with horizontal and vertical sides, and two vertices are adjacent if and only if their rectangles can be connected by a horiz...