We present an efficient parallel algorithm for constructing rectangular duals of plane triangular graphs. This problem finds applications in VLSI design and floor-planning problems. No NC algorithm for solving this pr...
详细信息
We present an efficient parallel algorithm for constructing rectangular duals of plane triangular graphs. This problem finds applications in VLSI design and floor-planning problems. No NC algorithm for solving this problem was previously known. The algorithm takes O(log(2) n) time with O(n) processors on a CRCW PRAM, where n is the number of vertices of the graph.
An irreducible triangulation is a plane graph such that its outer face is a quadrangle, every inner face is a triangle, and it has no separating triangle. Let T be an irreducible triangulation with n vertices. A recta...
详细信息
An irreducible triangulation is a plane graph such that its outer face is a quadrangle, every inner face is a triangle, and it has no separating triangle. Let T be an irreducible triangulation with n vertices. A rectangular dual R of T is a dissection of a rectangle into (small) rectangles such that (1) each rectangle of R corresponds to a vertex of T , and (2) two rectangles of R are adjacent if the two corresponding vertices of T are adjacent. Finding a rectangular dual of a given graph has an application on cartograms and VLSI floor-planning. In this paper, we consider the problem of enumerating all the rectangular duals of a given irreducible triangulation. It is known that the set of rectangular duals of an irreducible triangulation T one-to-one corresponds to the set of transversal edge-partitions of T . Hence, in this paper, we design an enumeration algorithm of all the transversal edge-partitions of an irreducible triangulation with n vertices. The proposed algorithm enumerates them in O ( n )-delay and O ( n 2 )-space after O ( n log n )-time preprocessing. (c) 2024 Elsevier B.V. All rights are reserved, including those for text and data mining, AI training, and similar technologies.
Contact graphs of isothetic rectangles unify many concepts from applications including VLSI and architectural design, computational geometry, and GIS. Minimizing the area of their corresponding rectangular layouts is ...
详细信息
Contact graphs of isothetic rectangles unify many concepts from applications including VLSI and architectural design, computational geometry, and GIS. Minimizing the area of their corresponding rectangular layouts is a key problem. We study the area-optimization problem and show that it is NP-hard to find a minimum-area rectangular layout of a given contact graph. We present O(n)-time algorithms that construct O(n(2))-area rectangular layouts for general contact graphs and O(n log n)area rectangular layouts for trees. ( For trees, this is an O(logn)-approximation algorithm.) We also present an infinite family of graphs (respectively, trees) that require Omega(n(2)) ( respectively, Omega(n log n)) area. We derive these results by presenting a new characterization of graphs that admit rectangular layouts, using the related concept of rectangular duals. A corollary to our results relates the class of graphs that admit rectangular layouts to rectangle-of-influence drawings.
暂无评论