Unit Rectangle Visibility Graphs

Details Unit Rectangle Visibility Graphs Unit Rectangle Visibility Graphs

2007-10-11

arxiv.org/abs/0710.2279v1

Mathematics

Combinatorics

27 Pages, 25 figures

Scientific paper

Over the past twenty years, rectangle visibility graphs have generated considerable 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.

Affiliated with

Also associated with

No associations

Rating

Unit Rectangle Visibility Graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Unit Rectangle Visibility Graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Unit Rectangle Visibility Graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-541984