  We study the maximum induced matching problem on a graph g. Induced matchings
correspond to independent sets in L2(g), the square of the line graph of g. The
problem is NP-complete on bipartite graphs. In this work, we show that for a
number of graph families with forbidden vertex orderings, almost all forbidden
patterns on three vertices are preserved when taking the square of the line
graph. These orderings can be computed in linear time in the size of the input
graph. In particular, given a graph class G characterized by a vertex ordering,
and a graph g = (V, E) in G with a corresponding vertex ordering \sigma of V ,
one can produce (in linear time in the size of g) an ordering on the vertices
of L2(g), that shows that L2(g) in G - for a number of graph classes G -
without computing the line graph or the square of the line graph of g. These
results generalize and unify previous ones on showing closure under L2(.) for
various graph families. Furthermore, these orderings on L2(g) can be exploited
algorithmically to compute a maximum induced matching on G faster. We
illustrate this latter fact in the second half of the paper where we focus on
cocomparability graphs, a large graph class that includes interval,
permutation, trapezoid graphs, and co-graphs, and we present the first O(mn)
time algorithm to compute a maximum weighted induced matching on
cocomparability graphs; an improvement from the best known O(n4) time algorithm
for the unweighted case.
