Graph search algorithms, such as breadth-first search or depth-first search, are widely used for problems ranging from solving mazes, to traversing graphs, to evaluating artificial intelligence search trees. Graph search algorithms visit the vertices of a graph in a particular order, which can reveal structure in the graphs. Despite the wide-spread use of these algorithms, many structural properties of these vertex orderings have not been studied.

In this work, we consider the answer to a simple question: in the various types of graph search vertex orderings, how can a nonneighbouring vertex be visited before a neighbouring vertex? The surprising answers turn out to characterize a variety of known search algorithms, and leads to the identification of two new types of graph searches, completing our graph search hierarchy.

We will show how this new view of graph search vertex orderings lead to applications, such as recognition of classes of graphs, finding orderings of powers of graphs, and computing minimal triangulations of graphs.

Portions of this work is joint with Derek Corneil, Anne Berry and Genevieve Simonet.