  We introduce I/O-optimal certifying algorithms for bipartite graphs, as well
as for the classes of split, threshold, bipartite chain, and trivially perfect
graphs. When the input graph is a class member, the certifying algorithm
returns a certificate that characterizes this class. Otherwise, it returns a
forbidden induced subgraph as a certificate for non-membership. On a graph with
$n$ vertices and $m$ edges, our algorithms take optimal $O(\text{sort}(n + m))$
I/Os in the worst case or with high probability for bipartite chain graphs, and
the certificates are returned in optimal I/Os. We give implementations for
split and threshold graphs and provide an experimental evaluation.
