In 2015 I started implementing the 1979 algorithm by Lipton and Tarjan for partitioning a planar graph. This theorem has been used to theoretically solve hundreds of other problems. However, at the time of graduation I was only 90% complete it, and have been busy with other projects to work on the other 90%. I’m hoping it can be included in the Boost Graph Library someday. If this is something you’d like to see completed or could help out with, let me know.

Code here: https://github.com/jeffythedragonslayer/lipton-tarjan

I started this project after looking for the most complicated algorithms in computer science and came across Bernard Chazelle’s paper for triangluating a polygon in linear time: https://www.cs.princeton.edu/~chazelle/pubs/polygon-triang.pdf I quickly realized the whole algorithm would take years to implement and would only be faster for polygons with an astronomically large number of edges. The Lipton-Tarjan algorithm is used as a subroutine.

Kudos to you for trying to finish a project you started. I always start with the best intentions, but then a new idea takes hold…

By the way that Princeton link really messes up the formatting on the line above it. Why not handle it like the first Princeton link?

Thanks. I still haven’the gotten around to formatting and layout design for this blog quite yet, but the important thing is the content is there.

Thanks for sharing, this is a fantastic blog.Really thank you! Great.