A Linear-Time Algorithm for Finding an Ambitus

Abstract:

We devise a linear-time algorithm for finding an ambitus in an
undirected graph. An ambitus is a cycle in a graph containing two
distinguished vertices such that certain different groups of bridges
(called B sup P-, B sup Q- and B sup PQ-bridges) satisfy the
property that a bridge in one group does not interlace with any bridge
in the other groups. Thus, an ambitus allows the graph to be cut into
pieces, where, in each piece, certain graph properties may be
investigated independently and recursively, and then the pieces can be
pasted together to yield information about these graph properties in
the original graph. In order to achieve a good time-complexity for
such an algorithm employing the divide-and-conquer paradigm, it is
necessary to find an ambitus quickly. We also show that, using
ambitus, linear-time algorithms can be devised for abiding-path-finding
and nonseparating-induced-cycle-finding problems.

This technical report has been published as

A Linear-Time Algorithm for Finding an Ambitus. B. Mishra and
Robert T. Tarjan, Algorithmica 7
(1992) 521-554.