Unit rectangle visibility graphs

zbMATH Open1179.05076arXiv0710.2279MaRDI QIDQ1010802FDOQ1010802

Authors: J. Martínez 

Publication date: 7 April 2009

Published in: The Electronic Journal of Combinatorics (Search for Journal in Brave)

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 $K_n$, $K_{m,n}$, and trees to be URVGs, as well as a number of general edge bounds.

Full work available at URL: https://arxiv.org/abs/0710.2279

File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Recommendations

• scientific article; zbMATH DE number 2068172
• scientific article; zbMATH DE number 1962799
• Rectangle-visibility representations of bipartite graphs
• Area, perimeter, height, and width of rectangle visibility graphs
• Unit stack visibility graphs
• RECTANGLE AND BOX VISIBILITY GRAPHS IN 3D
• Unit-length rectangular drawings of graphs
• scientific article; zbMATH DE number 1472168
• Combinatorial properties and recognition of unit square visibility graphs
• Combinatorial properties and recognition of unit square visibility graphs

zbMATH Keywords

edge bound resultsrectangle visibility graphsunit rectangle visibility graphURVGVLSI chip design

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Graph representations (geometric and intersection representations, etc.) (05C62) Applications of graph theory to circuits and networks (94C15) Hardware implementations of nonnumerical algorithms (VLSI algorithms, etc.) (68W35)

Cited In (9)

• Visibility representations of boxes in 2.5 dimensions
• Unit hypercube visibility numbers of trees
• Graph Drawing
• Combinatorial properties and recognition of unit square visibility graphs
• Combinatorial properties and recognition of unit square visibility graphs
• Area, perimeter, height, and width of rectangle visibility graphs
• DISTANCE VISIBILITY GRAPHS
• Representing 3-trees as unit rectangle-visibility graphs
• Colored anchored visibility representations in 2D and 3D space

This page was built for publication: Unit rectangle visibility graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1010802)