Implementing the Lipton-Tarjan Planar Separator Theorem

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.

5 thoughts on “Implementing the Lipton-Tarjan Planar Separator Theorem

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.

Leave a Reply

Your email address will not be published. Required fields are marked *