Marc Tedder

Applications of Lexicographic Breadth-First Search to Modular Decomposition, Split Decomposition, and Circle Graphs
PhD Thesis, Marc Tedder.


The thesis consists of three main results: a simpler modular decomposition algorithm, efficient split decomposition using graph-labelled trees, and the first sub-quadratic circle graph recognition algorithm. The first of these three results appeared at ICALP 2008 (see below); the other two are currently being prepared for journal submission.

Simpler, Linear-Time Modular Decomposition via Recursive Factorizing Permutations,
by Marc Tedder, Derek Corneil, Michel Habib, and Christophe Paul.

This paper appeared at ICALP 2008 and is published in its proceedings; a copy of the article is found below. Also below is an implementation of the algorithm described in the paper, written in Java. The code is intended only for demonstration purposes, and appears here to answer questions I received in presenting the algorithm to different audiences. The code should be considered provisional in that it has not been thoroughly tested, and because I intend to improve it in the future. It is also worth noting that the code does not include much in the way of error-checking.

The paper, The Code