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 be an irreducible triangulation with vertices. A rectangular dual of is a dissection of a rectangle into (small) rectangles such that (1) each rectangle of corresponds to a vertex of , and (2) two rectangles of are adjacent if the two corresponding vertices of 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 one-to-one corresponds to the set of transversal edge-partitions of . Hence, in this paper, we design an enumeration algorithm of all the transversal edge-partitions of an irreducible triangulation with vertices. The proposed algorithm enumerates them in -delay and -space after -time preprocessing.

A ladder lottery , known as “Amidakuji” in Japan, is a common way to decide an assignment at random. In this paper, we investigate reconfiguration and enumeration problems of cyclic ladder lotteries. First, when a permutation π and an optimal displacement vector x are given, we investigate the reconfiguration and enumeration problems of the “optimal” cyclic ladder lotteries of π and x . Next, for a given permutation π we consider reconfiguration and enumeration problems of the optimal displacement vectors of π .