A linear-time certifying algorithm for recognizing generalized series–parallel graphs

The problems of recognizing series–parallel graphs, outerplanar graphs, and generalized series–parallel graphs have been studied separately in the past. Efficient algorithms have been presented. However, none of the algorithms are certifying. A certifying algorithm generates, in addition to its answer, a certificate that can be used by a checker (a separate algorithm) to verify the correctness of the answer. The certificate is positive if the answer is ‘yes’, and is negative if the answer is ‘no’. In this paper, an -time certifying algorithm that simultaneously determines if a graph is series–parallel, outerplanar, or generalized series–parallel is presented. The positive certificates are a construction sequence for constructing if is series–parallel, a generalized construction sequence for constructing if is generalized series–parallel but not series–parallel, and the edge set of the exterior boundary of an outerplanar embedding of if is outerplanar. The negative certificates are forbidden subgraphs or forbidden structures of . All these certificates are generated by making only one pass over after a preprocessing step decomposing into its biconnected components.