Background is in computer science, but I realize I'm well and fully into graph-theory, here.
I have constructed the following bipartite graph where each node represents either a vertical or horizontal chord of a polygon. I construct an edge between the nodes if the two chords intersect or share a vertex.
As I understand it* (and implemented it), the Maximum Flow algorithm can be used to find the Maximum Independent Set in the following manner:
*not guaranteed to be correct, mind!
Convert the bipartite graph into a directed graph, adding a "universal source" and "ultimate sink" node to the graph, to get this:
Next, find a path from Source to Sink (I implemented a Depth-first search). Once you find a valid path, reverse the directions of the edges along the path, and try to find a new path. After all paths from Source -> Sink have been exhausted, the edges of the new graph that go from h -> v form... a matching? (At this point, my knowledge of terminology breaks down).
The iterations of said algorithm (I think this is equivalently the Hungarian Maximum Matching method?) look like this:
Which gives us 3 edges which meet the "h -> v" criteria, h1 -> v3, h2 -> v1, and h3 -> v2:
Of which the maximum independent set is one of either pair of nodes, so "v1, v2, v3" would be a maximum independent set, as would "v2, h2, h3".
(I believe for completeness I may also need to add any v or h nodes that do not have any edges other than to Sink or Source).
Long story short, am I way off base here? Am I missing some step or fundamentally misunderstanding how to calculate what I'm looking for? The data I'm comparing against suggests and answer of v2, h2, h3 (or u1, r2, r3 in this diagram), but it also mentions that there are multiple maximally independent sets that are equivalent, just with different nodes.
Anyway, am I way off-base here? I feel like I'm 90% of the way there, and I'm just not fully grasping how to go from (b) to (c). Any help? (Or at least a start pointing me in the appropriate direction to know how I can learn more relevant graph stuff!)
