Unit Rectangle Visibility Graphs

Report
Unit Rectangle
Visibility Graphs
Sarah Hamilton*
Saint Michael’s College, Vermont
Collaborating Authors:
Greta Pangborn, Joanna Ellis-Monaghan, and Alice Dean
* Research supported by NASA under Training Grant NGT5-40110 to the
Vermont Space Grant Consortium.
Quick Review of Graph Theory
 Review of Visibility Graphs
 Introduction to Unit Rectangle Visibility
Graphs
 Our Results
 Acknowledgements
 Further Reading

Important Concepts from Graph Theory

Cn : Cycle on n vertices

Trees – no cycles and connected

Caterpillar – a tree that consists of a maximum
length path (its spine) together with a set of
vertices each of which is adjacent to a vertex
on the spine.

Forest – a collection of trees
C5

K n : Complete graph on n
vertices
K5

A Bar Visibility layout of a graph:



Represents each node as a bar in the plane
Represents edges as unobstructed vertical visibilities between the
corresponding bars.
Unit Bar Visibility Graphs (UBVGs) have the additional restriction that
the bars have unit length.
Unit Rectangle Visibility Graphs

A Rectangle Visibility layout of a graph:

Represents each node as a rectangle in the plane
 Represents edges as unobstructed horizontal or vertical visibilities
between the corresponding rectangles.

Unit Rectangle Visibility Graphs (URVGs) restrict the rectangles in
the layout to be unit squares

URVGs more accurately model the fixed-size components needed for
chip layouts
Why Study URVGs?
?
?

Computer chip design begins with a netlist, an abstract description of thousands of
logical gates with intricate wiring connections and timing constraints among them.

VLSI chip design and layout problems (BVGs and RVGs)

Fixed area and aspect ratios of computer chips

This leads us to investigate RVGs with unit rectangles as providing a more accurate
model for chip design applications.

In a chip design model, the rectangles may represent gates or other components, while
the visibilities represent the wires. The edges of rectangle are also of interest because
they can be easily partitioned in two sets, one containing the horizontal edges, the other
containing the vertical edges of a visibility layout. This is important in chip design since
each layer in a chip has wires running alternately in the x or y direction.
Cycles


Any cycle, Cn, on n vertices is a non-collinear unit rectangle visibility
graph.
If v is a vertex of a URVG G and deg(v) ≥ 7, then v is in a cycle of G.
Why is this true?



GH – subgraph corresponding to horizontal edges in G
GV – subgraph corresponding to vertical edges in G
GV has UBV layout given by bottommost sides of the squares (similar for GH
leftmost)
Consider a URV layout where v has deg ≥ 7,
 By the pigeonhole principle either GV or GH has 4 edges adjacent to v
 Contradiction to Dean and Veytsel’s result that any vertex in a UBVG with
deg ≥ 4 lies on a cycle.

A URVG tree T has maximum degree ≤ 6.
URVG Results – Complete Graphs

K4 is the largest complete graph that is a URVG.
1
1
4
2
2
4
3
3

Why isn’t K5 a URVG?

In order to layout K3 where the lower left hand corner of the squares of have
coordinates (x1, y1), (x2, y2), and (x3, y3) one of the sequences (x1, x2, x3) or
(y1,y2,y3) must be non-monotonic.
 When you look at five squares (assuming wlog that x1 ≤ x2 ≤ x3 ≤ x4 ≤ x5) there
must be a monotonic subsequence of length 3 in the sequence (y1, y2, y3, y4, y5)
1
1
2
5
2
5
4
3
3
4




A caterpillar is a tree that
consists of a maximum length
path (its spine) together with
set of vertices adjacent to the
spine vertices.
A subdivided caterpillar allows
each edge to be replaced by a
path.
A caterpillar (or a subdivision
of a caterpillar) is a URVG if
and only if it has a spine such
that deg(v) ≤ 6 for all spine
vertices.
In the picture to the right, the
red vertices represent the
spine.
UBVG Trees

If T is a tree with maximum degree 3, and T is a
subdivision of a caterpillar, then T is a UBVG. [Dean and
Veytsel]
s

 2k  1
A maximal depth-s UBV tree has at most k 0
vertices and is isomorphic to G, which has UBV layout
LG (see Figure below).
LG
G
URVG Trees

T is a URVG tree iff it can be decomposed into two caterpillar UBVG forests where
every vertex (in the UBVG forest) has deg ≤ 3 (Conjecture-Almost proved).
u
w
Depth-1 tree
Depth-2 tree
s

Given a maximal URVG tree T (depth s ≥ 1) , TV has exactly
s
s
where
a
k 1
as   (2k  1)as k ; a0  1 and Cs   (2k  1).
k 1
k 1
C( s 1)k edges
k 1
Complete Bipartite Graphs Km,n

Km,n (with m ≤ n) is a URVG if and only if m ≤ 2 and n ≤ 6 or m=3 and n=4.

A weak URVG layout allows extra visibilities between rectangles where there are no
edges in the original graph.

Km,n (with m ≤ n) is a weak URVG if and only if m ≤ 2 (n arbitrary) or m=3 and n ≤ 4.

URV Layouts K2,6 and K3,4

Weak URV Layout of K2,n
Edge Bounds
If G is a URVG with n vertices, then
| E (G) | 6n  4  n   1
Why is this true? Surround a URV layout with four
rectangles (as in the picture on the right).
Hutchinson, Shermer, and Vince prove an upper bound
for the number of edges in an RVG which gives that the
number of edges in our modified graph is at most
6(n+4)-20
To get a bound for the original graph we can subtract the
number of edges (6) that connect nodes in the set {N, W,
S, E} and a lower bound on the number of edges
connecting one of the original nodes to one of the new
nodes (computed by looking at the perimeter of a
rectangle containing the original nodes).
For all n ≥ 64, there is a URVG on n vertices with at least 6n  12  n   6
 
edges.
Acknowledgements
This work was supported by VT EPSCoR
under grant NSF EPS 0236976 and by
NASA under Training Grant NGT5-40110
to the Vermont Space Grant Consortium.
Closing Remarks

New area of research

Applicability to computer chip layout

Still much more to do!

My experience as a first time researcher
Further Reading

For more detailed information on the proofs and
ideas presented in this talk
[email protected]

For more information about Erdös and Szekeres
see:
P. Erdos and A. Szekeres. A combinatorial problem
in geometry. Compositio Mathematica, 2:463470, 1935.
More
information
on
BVGs
Alice M. Dean, William Evans, Ellen Gethner, Joshua D. Laison,

Mohammad Ali Safari, and William T. Trotter. Bar k-visibility
graphs. 2005.

Mike Develin, Stephen Hartke, and David Petrie Moulton. A
general notion of visibility graphs. Discrete & Computational
Geometry, 29(4):511-524, 2003.

Stephen G. Hartke, Jennifer Vandenbussche, and Paul Wenger.
Further results on bar k-visibility graphs. 2005.

Stephen K. Wismath. Characterizing bar line-of-sight graphs. In
SCG '85: Proceedings of the first annual symposium on
Computational geometry, pages 147-152, New York, NY, USA,
1985. ACM Press.
More information on UBVGs
Alice M. Dean and Natalia Veytsel. Unit bar-visibility graphs.
Congressus Numerantium, 160:161{175, 2003.
More
information
on
RVGs
Prosenjit Bose, Alice M. Dean, Joan Hutchinson, and Thomas Shermer. On

rectangle visibility graphs. In Graph Drawing, volume 1190, pages 25-44,
1996.

Alice M. Dean and Joan P. Hutchinson. Rectangle-visibility representations
of bipartite graphs. In GD '94: Proceedings of the DIMACS International
Workshop on Graph Drawing, pages 159-166, London, UK, 1995. SpringerVerlag.

Alice M. Dean and Joan P. Hutchinson. Rectangle-visibility layouts of unions
and products of trees. Journal of Graph Algorithms and Applications, 2(8):121, 1998.

Thomas Shermer. On rectangle visibility graphs ii: k-hilly and maximumdegree 4. 1996.

Ileana Streinu and Sue Whitesides. Rectangle visibility graphs:
Characterization, construction, and compaction. In STACS '03: Proceedings
of the 20th Annual Symposium on Theoretical Aspects of Computer
Science, pages 26-37, London, UK, 2003. Springer-Verlag.
More information on RVGs in 3
dimensions

Prosenjit Bose, Hazel Everett, Sandor Fekete, Anna Lubiw, Henk Meijer, Kathleen
Romanik, Tom Shermer, and Sue Whitesides. On a visibility representation for graphs in
three dimensions. 1995.

Michael Burstein and Richard Pelavin. Hierarchical channel router. In DAC '83:
Proceedings of the 20th conference on Design automation, pages 591-597, Piscataway,
NJ, USA, 1983. IEEE Press.

Olivier Devillers, Hazel Everett, Sylvian Lazard, Maria Pentcheva, and Steven Wismath.
Drawing kn in three dimensions with one bend per edge. INRIA, (5708), September
2005.

Vida Dujmovic', David Eppstein, Matthew Suderman, and David R. Wood. Drawings of
planar graphs with few slopes and segments, 2006.

Sung-Chuan Fang, Kuo-En Chang, Wu-Shiung Feng, and Sao-Jie Chen. Constrained
via minimization with practical considerations for multi-layer vlsi/pcb routing problems. In
DAC '91: Proceedings of the 28th conference on ACM/IEEE design automation, pages
60-65, New York, NY, USA, 1991. ACM Press.

Sandor P. Fekete and Henk Meijer. Rectangle and box visibility graphs in 3d.
International Journal of Computational Geometry and Applications, 9(1):1-21, 1999.

D. R. Wood. Three-Dimensional Orthogonal Graph Drawing. School of Computer
Science and Software Engineering, Monash University, Australia 3168, 2000.
More information on Thickness of
Graphs

Michael B. Dillencourt, David Eppstein, and Daniel S.
Hirschberg. Geometric thickness of complete graphs.
Journal of Graph Algorithms and Applications, 4(3):5-17,
2000.

Joan P. Hutchinson, Thomas Shermer, and Andrew Vince.
On representations of some thickness-two graphs.
Computational Geometry, 13:161-171, 1999.

Petra Mutzel, Thomas Odenthal, and Mark Scharbrodt. The
thickness of graphs: A survey. 1998.

David R. Wood and Jan Arne Telle. Planar decompositions
and the crossing number of graphs with an excluded minor,
2006.
Thank You for Coming!

similar documents