A graph G is a tolerance graph if and only if each vertex v ∈ V (G) can be associated with an interval Iv of the real numbers and a positive real number tv with uv ∈ E(G) if and only if |Iv ∩ Iu | ≥ min{tv , tu }. Graph G is a probe interval graph if there is a partition of V (G) into sets P and N with each vertex associated to an interval of the real number line such that uv ∈ E if and only if Iu ∩ Iv ̸= Ø and {u, v} ∩ P ̸= Ø. We give a recognition algorithm for bipartite tolerance graphs that yields a structural characterization in terms of 2-connected blocks. With a few modifications, the same recognition algorithm works for bipartite probe interval graphs and yields a structural characterization for them in terms of 2-edge-connected blocks. The recognition algorithm is O(|V | + |E|) for both classes of graphs.
Available at: http://works.bepress.com/david_brown/4/