Efficient enumeration of transversal edge-partitions.

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. [ABSTRACT FROM AUTHOR]