{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,8,10]],"date-time":"2024-08-10T00:02:28Z","timestamp":1723248148720},"reference-count":0,"publisher":"Wiley","issue":"1","license":[{"start":{"date-parts":[[2000,1,1]],"date-time":"2000-01-01T00:00:00Z","timestamp":946684800000},"content-version":"vor","delay-in-days":2346,"URL":"http:\/\/creativecommons.org\/licenses\/by\/3.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["VLSI Design"],"published-print":{"date-parts":[[1996,1]]},"abstract":"<jats:p>The compaction step of integrated circuit design motivates associating several kinds of graphs with a collection of non\u2010overlapping 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\u2010 and cost\u2010optimal 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 <jats:italic>n<\/jats:italic> non\u2010overlapping rectangles as input, both these structures can be constructed in \u03b8(log <jats:italic>n<\/jats:italic>) time using n processors in the CREW model.<\/jats:p>","DOI":"10.1155\/1996\/40175","type":"journal-article","created":{"date-parts":[[2007,9,18]],"date-time":"2007-09-18T12:56:50Z","timestamp":1190120210000},"page":"33-40","source":"Crossref","is-referenced-by-count":0,"title":["Time\u2010 and Cost\u2010Optimal Parallel Algorithms for the Dominance and Visibility Graphs"],"prefix":"10.1155","volume":"4","author":[{"given":"D.","family":"Bhagavathi","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"H.","family":"Gurla","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"S.","family":"Olariu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"J. L.","family":"Schwing","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"J.","family":"Zhang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"311","published-online":{"date-parts":[[1993,7,30]]},"container-title":["VLSI Design"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/downloads.hindawi.com\/archive\/1996\/040175.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/downloads.hindawi.com\/journals\/vlsi\/1996\/040175.xml","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1155\/1996\/40175","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,8,9]],"date-time":"2024-08-09T15:21:20Z","timestamp":1723216880000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1155\/1996\/40175"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1993,7,30]]},"references-count":0,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1996,1]]}},"alternative-id":["10.1155\/1996\/40175"],"URL":"https:\/\/doi.org\/10.1155\/1996\/40175","archive":["Portico"],"relation":{},"ISSN":["1065-514X","1563-5171"],"issn-type":[{"type":"print","value":"1065-514X"},{"type":"electronic","value":"1563-5171"}],"subject":[],"published":{"date-parts":[[1993,7,30]]}}}