On the Characterization of Classes of Floorplans by Pattern-Avoiding Permutation Matrices

Let R be an axis-aligned rectangle. We define a floorplan as a partition of R into rectangular regions (rooms) such that each vertex is shared by at most three rooms. Following the approach of Nakano et al.,we also assume the presence of a set of points that impose constraints on the walls passing through them, allowing only horizontal or vertical segments. These constraints can be encoded by a permutation matrix whose entries are labeled H and V, which we refer to as a pattern matrix. In this work, we characterize the well-known classes of guillotine, diagonal, and diagonal–guillotine floorplans in terms of the presence of specific families of pattern matrices. In this way, we translate a purely geometric characterization into a combinatorial one.