S-visibility problem in VLSI chip design

Authors

MARZIEH ESKANDARI
MAHDIEH YEGANEH

DOI

10.3906/elk-1608-281

Abstract

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.

Keywords

Symbolic layout, visibility, dynamic programming, VLSI design

First Page

3960

Last Page

3969

Recommended Citation

ESKANDARI, MARZIEH and YEGANEH, MAHDIEH (2017) "S-visibility problem in VLSI chip design," Turkish Journal of Electrical Engineering and Computer Sciences: Vol. 25: No. 5, Article 37. https://doi.org/10.3906/elk-1608-281
Available at: https://journals.tubitak.gov.tr/elektrik/vol25/iss5/37