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.