Partition a square into sub-rectangles with restrictions - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-19T23:10:07Z http://mathoverflow.net/feeds/question/64942 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/64942/partition-a-square-into-sub-rectangles-with-restrictions Partition a square into sub-rectangles with restrictions Mohammad Al-Turkistany 2011-05-13T21:55:29Z 2011-12-18T04:39:16Z <p>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:</p> <p>1- No vertical line crosses any horizontal line and vice versa.</p> <p>2- Each vertical line touches exactly three horizontal lines and each horizontal line touches exactly three vertical lines.</p> <p>Here is an example when \$n=4\$</p> <p><img src="http://i.imgur.com/FbGDD.jpg" alt="enter image description here"></p> http://mathoverflow.net/questions/64942/partition-a-square-into-sub-rectangles-with-restrictions/64947#64947 Answer by Mark Sapir for Partition a square into sub-rectangles with restrictions Mark Sapir 2011-05-13T22:47:31Z 2011-05-13T22:47:31Z <p>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. </p> http://mathoverflow.net/questions/64942/partition-a-square-into-sub-rectangles-with-restrictions/83768#83768 Answer by Stuart Anderson for Partition a square into sub-rectangles with restrictions Stuart Anderson 2011-12-18T04:39:16Z 2011-12-18T04:39:16Z <p>"I'm looking for explicit algorithm to construct contact graphs that correspond to cubic planar bipartite graphs" I suggest you use plantri <a href="http://cs.anu.edu.au/~bdm/plantri/" rel="nofollow">http://cs.anu.edu.au/~bdm/plantri/</a> to generate the graphs.</p> <p>represent the graphs as vertex-edge incidence matrices A slice a row from A to get A'</p> <p>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</p> <p>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</p> <p>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</p> <p>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</p> <p>refer to electrical network theory, squared rectangles, brooks, smith , tutte &amp; stone, kenyon, etc</p> <p>Stuart Anderson</p>