Title:  The power of graph searching for the development of fast, simple graph algorithms

Breadth First Search (BFS) and Depth First Search (DFS) have long been known to play an important role in graph algorithms, with applications ranging from network flows to planar graph recognition. In 1976, Rose, Tarjan and Lueker introduced Lexicographic Breadth First Search (LBFS), a restriction of BFS, and showed that LBFS yields a very simple chordal graph recognition algorithm. Somewhat surprisingly, little work was done on LBFS until the mid 1990s when it was shown that it had applications for other graph families, most notably AT-free graphs. A few years ago, Lexicographic Depth First Search (LDFS) was introduced; however, at that point no applications of LDFS were known.
In this talk, we will survey recent applications of LBFS to various problems including new simpler algorithms for both Modular Decomposition and Split Decomposition as well as the first subquadratic algorithm for circle graph recognition. Furthermore, applications of LDFS to cocomparability graphs will be presented. From this work we see that LDFS reveals interesting insights into, and new algorithms for, posets.
Many of these results are coauthored with students and other colleagues who will be named during the talk.