Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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$

enter image description here

share|improve this question

2 Answers 2

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.

share|improve this answer
Thanks Mark. There is a theorem which states that every planar bipartite graph is representable by a contact graph of horizontal and vertical line segments. I'm looking for explicit algorithm to construct contact graphs that correspond to cubic planar bipartite graphs. –  Mohammad Al-Turkistany May 14 '11 at 18:06
@Mohammad: It is interesting! I did not know about it. Whose theorem is it? –  Mark Sapir May 14 '11 at 20:46
Here is the paper: de Fraysseix, de Mendez, and Pach: Representation of planar graphs by segments, in: Intuitive Geometry. –  Mohammad Al-Turkistany May 14 '11 at 22:17
@Mohammad: Thanks! –  Mark Sapir May 15 '11 at 6:03

"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

share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.