Partition a square into sub-rectangles with restrictions

Question

Is there an algorithm to generate all partitions of given square by using $n$ vertical and $n$ horizontal lines into sub-rectangles under the following restrictions:

1- No vertical line crosses any horizontal line and vice versa.

2- Each vertical line touches exactly three horizontal lines and each horizontal line touches exactly three vertical lines.

3- No internal line touchs both boundary lines.

Here is an example when $n=4$

P.S. It appears that those partitions have connection to many different combinatorial structures. Such partitions are similar to Tatami tilings. Also, it seems that these partitions are related to planar straight-line drawing of cubic planar bipartite graphs $G(V_1, V_2, E)$ where horizontal lines represent the vertices of $V1$ and vertical lines represent the vertices of $V2$.

What algorithms are known which take a cubic planar bipartite graph and produce the corresponding restricted square partition?

I am also interested in any references that survey related combinatorial structures.

Answer 1

Yes the algorithm exists. For each $n$ consider the bi-partite graph $(H\cup V,E)$ where vertices are lines: horizontal and vertical, edges correspond to intersections, $|H|=|V|=n$. For every such graph try to realize it by a partition of the square. It is easy to check if that is possible (it is a system of polynomial equations which you can solve using, say, Groebner basis). This gives a (very slow) algorithm. It is clear that the problem of checking if the graph is "good" is in NP. Whether it is in P is an interesting question. It is quite possible it is in P.

Answer 2

"I'm looking for explicit algorithm to construct contact graphs that correspond to cubic planar bipartite graphs" I suggest you use plantri http://cs.anu.edu.au/~bdm/plantri/ to generate the graphs.

represent the graphs as vertex-edge incidence matrices A slice a row from A to get A'

multiply A' by its transpose to get the Kirchoff (or discrete Laplacian) matrix Using kirchhoffs laws for current and voltage we get A'x = b solving we invert K and find its determinant using LU decomposition x is the voltage vector of the nodes, this gives the horizontal line heights

if you performed the same operation with the dual graph of the graph used to get matrix A, you would end up with the vertical line positions

multiplying A' * K^-1 * A we get the branch (or edge ) currents matrix, each row corresponds to a different set of solutions, the currents are the lengths of the horizontal line segments and the dual graph gives the lengths of the vertical line segments

These are actually dissections of rectangles into squares, but dissections of squares into rectangles can be achieved by using outside algebraic constraints or by using a conductance matrix C A'*C*transpose(A') instead of just A*A' above

refer to electrical network theory, squared rectangles, brooks, smith , tutte & stone, kenyon, etc

Stuart Anderson