S-visibility problem in VLSI chip design

In this paper, a new version of very large scale integration (VLSI) layouts compaction problem is considered. Bar visibility graph (BVG) is a simple geometric model for VLSI chip design and layout problems. In all previous works, vertical bars or other chip components in the plane model gates, as well as edges, are modeled by horizontal visibilities between bars. In this study, for a given set of vertical bars, the edges can be modeled with orthogonal paths known as staircases. Therefore, we consider a new version of bar visibility graphs (BsVG). We then present an algorithm to solve the s-visibility problem of vertical segments, which can be implemented on a VLSI chip. Our algorithm determines all the pairs of segments that are s-visible from each other.

PDF

___

[1] Dean AM, Veytsel N. Unit bar-visibility graphs. In: 2003 Southeastern International Conference on Combinatorics, Graph Theory, and Computing; 3{7 March 2003; Boca Raton, FL, USA. pp. 161-175.
[2] Schlag M, Luccio F, Maestrini P, Lee D, Wong C. Visibility problem in VLSI layout compaction. Adv Comput Res 1985; 2: 259-282.
[3] Tamassia R, Tollis IG. A uni ed approach to visibility representations of planar graphs. Discrete Comput Geom 1986; 1: 321-341.
[4] Wismath SK. Characterizing bar line-of-sight graphs. In: ACM 1985 Symposium on Computational Geometry; 5{7 June 1985; Baltimore, MD, USA. New York, NY, USA: ACM. pp. 147-152.
[5] Lodi E, Pagli L. A VLSI solution to the vertical segment visibility problem. IEEE T Comput 1986; 35: 923-928.
[6] Bose P, Dean A, Hutchinson J, Shermer T. On rectangle visibility graphs. Graph Drawing 1996; 1190: 25-44.
[7] Dean AM, Ellis-Monaghan JA, Hamilton S, Pangborn G. Unit rectangle visibility graphs. Electron J Comb 2008; 15: 1-24.
[8] Dean AM, Hutchinson JP. Rectangle-visibility representations of bipartite graphs. Discrete Appl Math 1997; 75: 9-25.
[9] Streinu I, Whitesides S. Rectangle visibility graphs: characterization, construction, and compaction. Lect Notes Comput Sci 2003; 2607: 26-37.
[10] Carmi P, Friedman E, Katz MJ. Spiderman graph: Visibility in urban regions. Comp Geom 2015; 48: 251-259.