A new LBFS-based algorithm for cocomparability graph recognition

How much can you learn about the structure of a given graph, using a series of successive graph searches? We consider here cocomparability graphs which are the complement of the graphs that admit a transitive orientation (comparability graphs). We study the use of a series of successive LBFS searches in order to capture the structure of these graphs. On cocomparability graphs many problems like coloring, Hamilton path, maximal clique which are NP-complete in the general case can be solved in polynomial time. For all those problems a decisive step is to find a cocomp ordering. We will prove the correctness of an algorithm to find a cocomp ordering using |V(G)| successive LBFS. Our main result answers a question asked in Corneil, Olariu and Stewart [2009] about the existence of a multisweep LBFS algorithm for cocomparability graphs, and lays the foundation of a simple linear time multisweep LBFS algorithm to find a cocomp ordering.