<p>Starting with 5,7,<span class="math-container">$f$</span> and <span class="math-container">$g$</span> is correct. In order to complete the maximum independent you can proceed as follows. First, delete the vertices that are reachable from an unmatched vertex via an alternating path (in your example 5,6,7,<span class="math-container">$e$</span>,<span class="math-container">$f$</span>,<span class="math-container">$g$</span>). This leaves a balanced bipartite graph (that is, it has the same number of vertices on each side), and you can simply add one of the two sides to your independent set. In your example, you get the maximum independent set <span class="math-container">$\{1,2,3,4,5,7,f,g\}$</span> or <span class="math-container">$\{a,b,c,d,5,7,f,g\}$</span>.   </p>

CC BY-SA 4.0
2020-01-10T22:52:09.927Z
2020-01-11T21:50:03.323Z
2020-01-11T21:50:03.323Z
Thomas Kalinowski
<p>Following <a href="https://mathoverflow.net/a/28350/150894">this answer on MathOverflow</a> and section 3 of <a href="https://arxiv.org/pdf/0908.3916.pdf" rel="nofollow noreferrer">the linked paper</a> by David Eppstein on how to split an orthogonal polygon into rectangles I came to a point where I just fail to understand how to proceed.</p>

<p><a href="https://i.sstatic.net/X2aaC.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/X2aaC.png" alt="orthogonal polygon sectioning example"></a></p>

<p>As you can see on my example image I have added all diagonals connecting two concave vertices each. The green ones do not have any intersections with other diagonals and thus can be applied immediately for sectioning. The other diagonals lead to the following intersection graph:</p>

<p><a href="https://i.sstatic.net/tqdBV.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/tqdBV.png" alt="example intersection graph"></a></p>

<p>The graph already shows a maximal matching as found by the <a href="https://en.wikipedia.org/wiki/Hopcroft%E2%80%93Karp_algorithm" rel="nofollow noreferrer">Hopcroft-Carp algorithm</a> in blue. (If you are interested in an easy step-by-step tutorial for applying it manually, I can recommend <a href="https://www.youtube.com/watch?v=CSUEVu-qUgM" rel="nofollow noreferrer">this YouTube video</a>.)</p>

<p>For the next step (choosing the good diagonals) Eppstein writes:</p>

<blockquote>
  <p>[...] ﬁnding the maximum
  number of disjoint good diagonals translates, in graph-theoretic terms, into ﬁnding a
  maximum independent set in a bipartite graph. By König’s theorem [49], in any n-
  vertex bipartite graph the maximum independent set has size n − M, where M is the
  cardinality of a maximum matching; an independent set of this size may be found from
  a maximum matching <strong>by partitioning the vertices according to the lengths of the shortest alternating paths from an unmatched vertex to the given vertex, and including the
  vertices at even levels of this partition</strong>.</p>
</blockquote>

<p>If I understood it correcty, I do not know how to determine this length for each node in my graph, as there are nodes unable to reach an unmatched node via an alternating path. Here is what I would assume is meant:</p>

<pre><code>Node | Alternating Path Length to unmatched Node
-----+------------------------------------------
  1  | ?
  2  | ?
  3  | ?
  4  | ?
  5  | 2 (5-e-7)
  6  | 1 (6-g)
  7  | 0 (7)
  a  | ?
  b  | ?
  c  | ?
  d  | ?
  e  | 1 (e-7)
  f  | 2 (f-6-g)
  g  | 0 (g)
</code></pre>

<p>According to this I would definitely choose 5, 7, f and g as good diagonals, wouldn't I? But there will be remaining intersections not resolvable by this information.</p>

<p>I asked this question in very short form and without an example on the linked MathOverflow page in a comment, but the question there already left primary school (*) and I'm not sure if I will get any reaction there.</p>

<p>(*) In Germany primary school has four grades and usually one switches to a secondary school at the age of 10.</p>

<graph-algorithms><computational-geometry>
How to choose good diagonals when partitioning an orthogonal polygon into rectangles?
Neonit
# How to choose good diagonals when partitioning an orthogonal polygon into rectangles?

(Asked by: username_0 on 2020-01-10)

Following this answer on MathOverflow and section 3 of the linked paper by David Eppstein on how to split an orthogonal polygon into rectangles I came to a point where I just fail to understand how to proceed.

As you can see on my example image I have added all diagonals connecting two concave vertices each. The green ones do not have any intersections with other diagonals and thus can be applied immediately for sectioning. The other diagonals lead to the following intersection graph:

The graph already shows a maximal matching as found by the Hopcroft-Carp algorithm in blue. (If you are interested in an easy step-by-step tutorial for applying it manually, I can recommend this YouTube video.)
For the next step (choosing the good diagonals) Eppstein writes:

[...] ﬁnding the maximum
  number of disjoint good diagonals translates, in graph-theoretic terms, into ﬁnding a
  maximum independent set in a bipartite graph. By König’s theorem [49], in any n-
  vertex bipartite graph the maximum independent set has size n − M, where M is the
  cardinality of a maximum matching; an independent set of this size may be found from
  a maximum matching by partitioning the vertices according to the lengths of the shortest alternating paths from an unmatched vertex to the given vertex, and including the
  vertices at even levels of this partition.

If I understood it correcty, I do not know how to determine this length for each node in my graph, as there are nodes unable to reach an unmatched node via an alternating path. Here is what I would assume is meant:
Node | Alternating Path Length to unmatched Node
-----+------------------------------------------
  1  | ?
  2  | ?
  3  | ?
  4  | ?
  5  | 2 (5-e-7)
  6  | 1 (6-g)
  7  | 0 (7)
  a  | ?
  b  | ?
  c  | ?
  d  | ?
  e  | 1 (e-7)
  f  | 2 (f-6-g)
  g  | 0 (g)

According to this I would definitely choose 5, 7, f and g as good diagonals, wouldn't I? But there will be remaining intersections not resolvable by this information.
I asked this question in very short form and without an example on the linked MathOverflow page in a comment, but the question there already left primary school (*) and I'm not sure if I will get any reaction there.
(*) In Germany primary school has four grades and usually one switches to a secondary school at the age of 10.

**Tags:** graph-algorithms, computational-geometry


---

## 1 answers

### Answer by username_1 on 2020-01-10. Score: 1 | Accepted answer

Starting with 5,7,$f$ and $g$ is correct. In order to complete the maximum independent you can proceed as follows. First, delete the vertices that are reachable from an unmatched vertex via an alternating path (in your example 5,6,7,$e$,$f$,$g$). This leaves a balanced bipartite graph (that is, it has the same number of vertices on each side), and you can simply add one of the two sides to your independent set. In your example, you get the maximum independent set $\{1,2,3,4,5,7,f,g\}$ or $\{a,b,c,d,5,7,f,g\}$.


---

