  Let H be a connected bipartite graph with n nodes and m edges. We give an
O(nm) time algorithm to decide whether H is an interval bigraph. The best known
algorithm has time complexity O(nm^6(m + n) \log n) and it was developed in
1997 [18]. Our approach is based on an ordering characterization of interval
bigraphs introduced by Hell and Huang [13]. We transform the problem of finding
the desired ordering to choosing strong components of a pair-digraph without
creating conflicts. We make use of the structure of the pair-digraph as well as
decomposition of bigraph H based on the special components of the pair-digraph.
This way we make explicit what the difficult cases are and gain efficiency by
isolating such situations.
