A recognition algorithm for a class of graphs is certifying
if it gives proofs of membership and non-membership. Proofs
of membership are typically a particular representation of
the graph and proofs of non-membership are typically forbidden
subgraphs of some sort. We discuss certifying recognition
algorithms for planar graphs (pages 23 -- 68) and
The worst case running time of some
graph algorithms can be improved considerably by the use of data structures:
Priority queues for shortest path calculations, dynamic trees for maximum f
flow, mergeable priorty queues for general weighted matching.
Is it worth the effort? We discuss the issue for shortest
general weighted matchings.