graph-theory

Implementation of the Lipton-Tarjan algroithm


Does anyone know of an implementation of the Lipton-Tarjan separator theorem for planar graphs algorithm? I couldn't find anything on Google, which surprised me considering how many times its been cited since 1979.

http://www.cs.princeton.edu/courses/archive/fall06/cos528/handouts/sepplanar.pdf


Solution

  • The only implementation I could find was an essay written by German students, where they explain their implementation (without complete source code though). => http://i11www.iti.uni-karlsruhe.de/_media/teaching/winter2006/algorithmengineering/ausarbeitung-pst.pdf

    But since these algorithms are used in a lot of other algorithms (for example divide and conquer), you should be able to find an implementation with source code in there somewhere.

    No matter if we'll find public source code: Yes, it's already been implemented.

    Kind regards