Linear Time Recognition Algorithms and Structure Theorems for Bipartite Tolerance Graphs and Bipartite Probe Interval Graphs
David E. Brown, Arthur H. Busch, Garth Isaak
Abstract
A graph is a probe interval graph if its vertices can be
partitioned into probes and nonprobes with an interval associated to
each vertex so that vertices are adjacent if and only if their
corresponding intervals intersect and at least one of them is a
probe. A graph G = (V,E) is a tolerance graph if each
vertex v ∈V can be associated to an interval
Iv of the real line and a positive real
number tv such that uv ∈E if
and only if |Iu ∩Iv|
≥ min (tu,tv). In
this paper we present O(|V| + |E|) recognition
algorithms for both bipartite probe interval graphs and bipartite
tolerance graphs. We also give a new structural characterization for
each class which follows from the algorithms.
Full Text: PDF PostScript