tailieunhanh - Báo cáo toán học: "Unit Rectangle Visibility Graphs"

Tuyển tập các báo cáo nghiên cứu khoa học về toán học trên tạp chí toán học quốc tế đề tài: Unit Rectangle Visibility Graphs. | Unit Rectangle Visibility Graphs Alice M. Dean Department of Mathematics and Computer Science Skidmore College Saratoga Springs NY adean@ Joanna A. Ellis-Monaghan Sarah Hamilton Department of Mathematics Department of Mathematics Saint Michael s College Colchester VT Saint Michael s College Colchester VT jellis-monaghan@ shamilton2@ Greta Pangbornz Department of Computer Science Saint Michael s College Colchester VT gpangborn@ Submitted Aug 27 2007 Accepted Jun 1 2008 Published Jun 6 2008 Mathematics Subject Classification 05C62 Abstract 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 Kn Km n and trees to be URVGs as well as a number of general edge bounds. Research supported by VT EPSCoR under grant NSF EPS 0236876 and the National Security Agency. y Research supported by NASA under Training Grant NGT5-40110 to the Vermont Space Grant Consortium. Research supported by VT EPSCoR under grant NSF EPS 0236876 and by NASA under Training Grant NGT5-40110 to the Vermont Space Grant Consortium. THE ELECTRONIC JOURNAL OF COMBINATORICS 15 2008 R79 1 1 Introduction Over the past twenty years the difficulty of VLSI chip design and layout problems has motivated the study of bar visibility graphs BVGs 3 5 6 11 12 16 17 and their two-dimensional .