1
$\begingroup$

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.

enter image description here

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:

enter image description here

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:

enter image description here enter image description here enter image description here

Which gives us 3 edges which meet the "h -> v" criteria, h1 -> v3, h2 -> v1, and h3 -> v2:

enter image description here

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!)

enter image description here

$\endgroup$
  • $\begingroup$ cs.stackexchange.com/q/3027 $\endgroup$ – Jean Marie Nov 24 '18 at 5:06
  • $\begingroup$ Besides, very nice presentation... But something puzzles me : what is the ultimate interest, in the context "points-straight lines" of having these maximal sets ? I ask it because I am very much interested in geometry, here "incidence geometry" which could be a good keyword for your searches. $\endgroup$ – Jean Marie Nov 24 '18 at 5:12
  • $\begingroup$ @JeanMarie - I am attempting to decompose the shape into rectangles, as per this research paper, "Rectangular Decomposition of Binary Images" by Suk, Höschl, and Flusser. $\endgroup$ – Raven Dreamer Nov 24 '18 at 5:20
  • $\begingroup$ Thanks for the reference. $\endgroup$ – Jean Marie Nov 24 '18 at 5:25
  • $\begingroup$ The Hungarian algorithm is not of the same nature as this one because it optimizes vertices selection with respect to weights cse.ust.hk/~golin/COMP572/Notes/Matching.pdf $\endgroup$ – Jean Marie Nov 24 '18 at 5:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.