3
$\begingroup$

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$

enter image description here

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.

  • 0
    @Amy, yes. If you don't count the 4 sides of the square then your $N= n-2$ but the restrictions must be observed for every horizontal and vertical line including the 4 sides of the square.2011-05-06

1 Answers 1

1

Look into work about what are called fault free tilings. Here is one paper of this kind: http://www.docstoc.com/docs/27537617/Fault--free-Tilings-of-Rectangle