Graph searching, a mechanism to traverse a graph visiting one vertex at a time in a specific manner, is a powerful tool used to extract structure from various families of graphs. Some families of graphs have a vertex ordering characterization, and we review how graph searching is used to produce such vertex orderings . These orderings expose structure that we exploit to develop efficient linear and near-linear time algorithms for some NP-hard problems (independent set, colouring, Hamiltonicity for instance).In this talk, we focus on two graph searches: Lexicographic breadth first search (LexBFS), and Lexicographic depth first search (LexDFS).
In particular, we will prove fixed point type theorems for LexBFS, and then focus on a LexDFS-based framework to lift algorithms from interval graphs to cocomparability graphs. If time permits, we will discuss the relationship between graph searches and graph convexities.