Open Access. Powered by Scholars. Published by Universities.®
Physical Sciences and Mathematics Commons™
Open Access. Powered by Scholars. Published by Universities.®
Articles 1 - 1 of 1
Full-Text Articles in Physical Sciences and Mathematics
Time- And Cost-Optimal Parallel Algorithms For The Dominance And Visibility Graphs, D. Bhagavathi, H. Gurla, S. Olariu, J. L. Schwing, J. Zhang
Time- And Cost-Optimal Parallel Algorithms For The Dominance And Visibility Graphs, D. Bhagavathi, H. Gurla, S. Olariu, J. L. Schwing, J. Zhang
Computer Science Faculty Publications
The compaction step of integrated circuit design motivates associating several kinds of graphs with a collection of non-overlapping rectangles in the plane. These graphs are intended to capture various visibility relations amongst the rectangles in the collection. The contribution of this paper is to propose time- and cost-optimal algorithms to construct two such graphs, namely, the dominance graph (DG, for short) and the visibility graph (VG, for short). Specifically, we show that with a collection of n non-overlapping rectangles as input, both these structures can be constructed in θ (log n) time using n processors in the CREW model.