Derek G. Corneil: Graph Searches, Cocomparability Graphs and Posets

Graph searching is a fundamental tool in the design of efficient, easily implementable graph algorithms. Breadth First Search (BFS) and Depth First Search (DFS) were described in the late 19th century as strategies for maze traversal and since the 1970s have been shown to have applications in such areas as distance calculation, network flows, and planar graph recognition. In a seminal paper in 1976, Rose, Tarjan and Lueker presented Lexicographic BFS (LBFS) and showed that it could be used to produce a linear time algorithm for recognizing chordal graphs (every cycle of length greater than 3 has a chord). Somewhat surprisingly, few other applications of LBFS were discovered until the mid 1990s. Since then, many new applications of LBFS have appeared, often using LBFS is a multisweeping fashion. Recent applications of LBFS include forming the foundation for new, efficient algorithms for both modular and split decomposition - two fundamental graph operations.

The success of LBFS raised the question of whether there is a similar Lexicographic version of DFS. Such a search was discovered almost 10 years ago, but only recently has it been shown to have applications, in particular to Partially Ordered Sets (posets) as well as to cocomparability graphs (graphs whose complement has a transitive orientation of its edges).

In this talk we survey these topics and present vertex ordering characterizations of various graph searching algorithms. The talk concludes with open questions.

Graphs, Hypergraphs, and Computing 14 January - 14 May 2014
Scientific leaders: Magnus M. Halldorsson, Klas Markström, Andrzej Rucinski, Carsten Thomassen