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
    Is this possible if $n \ge 3$?2011-05-06
  • 0
    Yes, it is possible.2011-05-06
  • 0
    I still cannot see it. Can you add an example picture to your question?2011-05-06
  • 0
    I would say that your picture has two horizontal and two vertical partitioning lines, each touching two of the other orientation; modulo symmetry I thing there are four such cases. If you regard it as four horizontal and four vertical partitioning lines, each touching three of the other orientation, then (ignoring its reflection) this may be the only case.2011-05-06
  • 0
    Isn't your picture for n=2? (two vertical and 2 horizontal lines added *inside* the square? Also, do you count a line touching a *side* of the square (perpendicular to it) as one of the three lines it touches? That seems to be the case in your picture2011-05-06
  • 0
    @Henry @Amy, sorry $n=4$ in my example. I'm looking for a general algorithm for any $n$.2011-05-06
  • 0
    So you *are* counting the edges of the square being partitioned as two vertical and two horizontal lines in n? Your initial question seems to imply that the square is *given*, and want to know how many possible partitions of the square exist when n horizontal and n vertical lines are constructed *inside* the square, such that...And I take it you mean that a horizontal line touching a vertical side of the square, e.g., counts as a "touch"...2011-05-06
  • 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