  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,Dalton, Habib (2013) and Dusart, Habib (2016) and 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 $O(n+mlogn)$ time algorithm to find a maximal
interval subgraph of a cocomparability graph. Similarly we propose a linear
time algorithm to compute all simplicial vertices in a cocomparability graph.
In both cases we improve on the current state of knowledge.
