How to choose good diagonals when partitioning an orthogonal polygon into rectangles?

Question

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:

[...] finding the maximum number of disjoint good diagonals translates, in graph-theoretic terms, into finding 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.

Answer 1

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\}$.