Partition a square into sub-rectangles with restrictions - MathOverflow

Partition a square into sub-rectangles with restrictions

2011-05-13T21:55:29Z

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.

Here is an example when $n=4$

Answer by Mark Sapir for Partition a square into sub-rectangles with restrictions

2011-05-13T22:47:31Z

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 by Stuart Anderson for Partition a square into sub-rectangles with restrictions

2011-12-18T04:39:16Z

"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