Geodesic
Unit rectangle visibility graphs
The electronic journal of combinatorics, Tome 15 (2008)
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

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.
DOI : 10.37236/803
Classification : 05C62, 05C85, 68R10, 68W35, 94C15
Mots-clés : rectangle visibility graphs, VLSI chip design, unit rectangle visibility graph, URVG, edge bound results 
@article{10_37236_803,
     author = {Alice M. Dean and Joanna A. Ellis-Monaghan and Sarah Hamilton and Greta Pangborn},
     title = {Unit rectangle visibility graphs},
     journal = {The electronic journal of combinatorics},
     year = {2008},
     volume = {15},
     doi = {10.37236/803},
     zbl = {1179.05076},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/803/}
}
TY  - JOUR
AU  - Alice M. Dean
AU  - Joanna A. Ellis-Monaghan
AU  - Sarah Hamilton
AU  - Greta Pangborn
TI  - Unit rectangle visibility graphs
JO  - The electronic journal of combinatorics
PY  - 2008
VL  - 15
UR  - http://geodesic.mathdoc.fr/articles/10.37236/803/
DO  - 10.37236/803
ID  - 10_37236_803
ER  - 
%0 Journal Article
%A Alice M. Dean
%A Joanna A. Ellis-Monaghan
%A Sarah Hamilton
%A Greta Pangborn
%T Unit rectangle visibility graphs
%J The electronic journal of combinatorics
%D 2008
%V 15
%U http://geodesic.mathdoc.fr/articles/10.37236/803/
%R 10.37236/803
%F 10_37236_803
Alice M. Dean; Joanna A. Ellis-Monaghan; Sarah Hamilton; Greta Pangborn. Unit rectangle visibility graphs. The electronic journal of combinatorics, Tome 15 (2008). doi: 10.37236/803

Cité par Sources :