Scalene rectangulation of a square: let me count the ways

Question

A rectangulation of a square is a dissection of the square $S$ into smaller rectangles $R_i$, $i=1,\ldots,n$ with the usual caveats: $S = \cup_i R_i$ and the interiors of distinct rectangles $R_i,R_j$ are disjoint.

We say a rectangulation is scalene if distinct rectangles (including the square $S$) do not have equal length sides of either parallel or perpendicular orientation.

Here is a square dissected into five smaller rectangles:

Figure 1: Scalene rectangulation layout for five rectangles

By a bit of perturbation in both axes separately, we can doubtless arrange none of the rectangles will have equal length sides. Up to the dihedral symmetries of a square and such axis-wise homotopy, this layout is unique (in allowing a scalene rectangulation of a square into five rectangles).

I am motivated by this previous Question to ask if the following layout using seven rectangles is similarly unique:

Figure 2: Scalene rectangulation layout for seven rectangles

More generally I am curious to count the scalene rectangulation layouts possible for each $n \ge 5$ (there are none for smaller $n$). I would like an algorithm that, given $n$, generates all the possible layouts for scalene rectangulation of a square into $n$ smaller rectangles. If the algorithm did not perfectly eliminate all redundancy, but still reduced the possible layouts to a manageable number, this would be an advance over my present understanding.

[To provide more context I will follow up this Question with a CW "answer" that summarizes what I've been able to glean from the literature and my own investigations.]

Answer 1

At least five rectangles are needed

One implication of a rectangulation being scalene is that two rectangles cannot meet exactly in a common side, i.e. not face-to-face as in a typical rectangular mesh generation (e.g. for finite elements).

Moreover the smaller rectangles cannot completely cover a side of the square $S$, so that each side of $S$ must include a vertex, a corner of a smaller rectangle. Thus the rectangles that cover the corners of the square must be distinct, giving a lower bound of four rectangles needed.

We can improve this to a minimum of five rectangles with the following:

Lemma If a rectangle $Q$ is dissected into:

• 2 smaller rectangles, then each has a side in common with $Q$ and also one between themselves.
• 3 smaller rectangles, then one has a side in common with $Q$, and the other two have a common side between themselves.
• 4 smaller rectangles, each has either a side in common with $Q$ or one with another of the smaller rectangles.

Proof: The first two propositions are fairly evident.

For the last, if one of the four smaller rectangles $R$ shares a side with $Q$, the other three rectangles dissect $Q\setminus R$ and we can rely on the early parts of this lemma. Otherwise none of the four smaller rectangles share a side with $Q$, and thus each covers exactly one corner of $Q$.

Fix any smaller rectangle $R = \overline{ABCD}$ (its corners in cyclic order), where $A$ is also a corner of $Q$. Let $S$ be the rectangle bordering $R$ at $B$, and let $T$ be the rectangle bordering $R$ at $D$.

The exterior angle of $R$ at $C$ is reflexive, so there must be at least two rectangles adjacent to $R$ at $C$ (by convexity). At least one of $S$ and $T$ must then be adjacent to $R$ at $C$ (by counting). $S$ and $T$ cannot both extend past $C$ without overlapping, and if either $S$ or $T$ terminates at $C$ then that rectangle would share a side with $R$.

That leaves the case that (say) $S$ is not adjacent to $R$ at $C$ and $T$ extends beyond $R$ at $C$. Since $S$ and $T$ would not be adjacent, the fourth smaller rectangle $U$ would need to fill that gap and thus $U$ be adjacent to $R$ at $C$. But then neither $S$ nor $U$ can block $T$ from extending past $C$ all the way to share a side with $Q$. Contradiction. █

With a bit of care we can read into this proof the conclusion that such a scalene layout of five rectangles is unique up to equivalence. However the seeming ad hoc presentation of geometric considerations make it an undesirable model for pursuing cases with even modestly more rectangles.

For example, I conjecture that there are no layouts with six rectangles, and that the layout with seven rectangles already illustrated is similarly unique. Ideally we will find a way to "arithmetize" our search for layouts, allowing for discrete algorithms to efficiently determine existence and uniqueness.

Casting a wide C-net

Many Readers will have noticed that these layouts define a planar graph whose vertices are shared corners of rectangles and whose edges are portions of a rectangle's boundary connecting two such vertices. Much investigation has been made of planar graphs whose "faces" (including the exterior face of a planar graph) can be realized as convex polygons bounding a polyhedron. It is not hard to see their (planar) duals are again of this kind.

In the literature on counting distinct polyhedral graphs (Duijvestijn and Federico, 1981; Duijvestijn, 1996), such a graph is often referred to as a $C$-net in respect of the combinatorial characterization of polyhedral graphs as $3$-vertex-connected planar graphs. The term order of a $C$-net is used to mean the number of edges.

Study of these stretches back to Euler's 1750 paper, "Elementa doctrinae solidorum," where he classified convex polyhedra according to Euler's famous formula:

$$ v + f = e + 2 $$

relating the numbers $v,f,e$ of vertices, faces, and edges. Our case is $f=8$ (octahedra), and the counts of possible $C$-nets (generically, without our geometric restrictions to rectangles with unequal sides) were known to Kirkman (1862):

Table 1. $C$-nets with eight faces

vertices    edges(order)     # of c-nets
    6            12                2
    7            13               11  
    8            14               42  
    9            15               74  
   10            16               76  
   11            17               38  
   12            18               14