  Strong cocomparability graphs are the reflexive graphs whose adjacency matrix
can be rearranged by a simultaneous row and column permutation to avoid the
submatrix with rows $01, 10$. Strong cocomparability graphs form a subclass of
cocomparability graphs (i.e., the complements of comparability graphs) and can
be recognized in polynomial time. In his seminal paper, Gallai characterized
cocomparability graphs in terms of a forbidden structure called asteroids.
Gallai proved that cocomparability graphs are precisely those reflexive graphs
which do not contain asteroids.
  In this paper, we give a characterization of strong cocomparability graphs
which is analogous to Gallai's characterization for cocomparability graphs. We
prove that strong cocomparability graphs are precisely those reflexive graphs
which do not contain weak edge-asteroids (a weaker version of asteroids). Our
characterization also leads to a polynomial time recognition algorithm for
strong cocomparability graphs.
