Unit rectangle visibility graphs

MaRDI QIDQ1010802zbMATH OpenFDO

Authors J. Martínez

Publication date 7 April 2009

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

Full work available at URL https://arxiv.org/abs/0710.2279, https://eudml.org/doc/117254, http://www.emis.de/journals/EJC/Volume_15/Abstracts/v15i1r79.html

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

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)

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.

Recommendations

• Publication:4464791
• Publication:4418634
• 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
• Publication:4489222
• Combinatorial properties and recognition of unit square visibility graphs
• Combinatorial properties and recognition of unit square visibility graphs

Cited in

(8)

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

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)