Unit Rectangle Visibility Graphs

Authors

Alice M. Dean, Skidmore College
Joanna A. Ellis-Monaghan, Saint Michael's College
Sarah J. Hamilton, Marquette UniversityFollow
Greta Pangborn, Saint Michael's College

Document Type

Article

Language

eng

Format of Original

24 p.

Publication Date

2007

Publisher

Electronic Journal of Combinatorics

Source Publication

Electronic Journal of Combinatorics

Source ISSN

1077-8926

Abstract

Over the past twenty years, rectangle visibility graphs have generated consider- able interest, in part due to their applicability to VLSI chip design. Here we study unit rectangle visibility graphs, with fixed dimension restrictions more closely modeling the constrained dimensions of gates and other circuit components in computer chip applications. A graph G is a unit rectangle visibility graph (URVG) if its vertices can be represented by closed unit squares in the plane with sides parallel to the axes and pairwise disjoint interiors, in such a way that two vertices are adjacent if and only if there is a non-degenerate horizontal or vertical band of visibility joining the two rectangles. Our results include necessary and sufficient conditions for K_n, K_m;n, and trees to be URVGs, as well as a number of general edge bounds.

Comments

Published version. Electronic Journal of Combinatorics, Vol. 15, No. R79 (2008). Permalink. © 2008 Electronic Journal of Combinatorics. Used with permission.

Sarah Hamilton was affiliated with St. Michael's College at the time of publication.

Recommended Citation

Dean, Alice M.; Ellis-Monaghan, Joanna A.; Hamilton, Sarah J.; and Pangborn, Greta, "Unit Rectangle Visibility Graphs" (2007). Mathematics, Statistics and Computer Science Faculty Research and Publications. 484.
https://epublications.marquette.edu/mscs_fac/484