Maximal Cliques Lattices Structures for Cocomparability Graphs with Algorithmic Applications.

A cocomparability graph is a graph whose complement admits a transitive orientation. An interval graph is the intersection graph of a family of intervals on the real line. In this paper we investigate the relationships between interval and cocomparability graphs. This study is motivated by recent results (Corneil et al., SIAM J. Comput. 42(3):792–807, 2013; Dusart et al., SIAM J. Comput. 50(3):1148–1153, 2021; Dusart and Habib, Discret. Appl. Math. 216:149–161, 2017) that show that for some problems, the algorithm used on interval graphs can also be used with small modifications on cocomparability graphs. Many of these algorithms are based on graph searches that preserve cocomparability orderings. First we propose a characterization of cocomparability graphs via a lattice structure on the set of their maximal cliques. Using this characterization we can prove that every maximal interval subgraph of a cocomparability graph G is also a maximal chordal subgraph of G. Although the size of this lattice of maximal cliques can be exponential in the size of the graph, it can be used as a framework to design and prove algorithms on cocomparability graphs. In particular we show that a new graph search, namely Local Maximal Neighborhood Search (LocalMNS) leads to an algorithm to find in linear time a maximal interval subgraph of a cocomparability graph which improves on the current state of knowledge. Although computing all simplicial vertices is known to be equivalent to the recognition of triangle-free graphs or boolean multiplication, see (Krastch and Spinrad, SIAM J. Comput. 36(2):310–325, 2007; Coudert and Ducoffe, SIAM J. Discrete Math. 32(1):682–694, 2018), we will show that our structural insights in cocomparability graphs together with the definition of a new graph search, allow us to achieve linear time on this class of graphs. [ABSTRACT FROM AUTHOR]