Algorithms for recognition of regular properties and decomposition of recursive graph families

This paper focuses on two themes within the broad context of recursively definable graph classes. First, the authors generalize the series-parallel operations and establish exactly how far they can be extended subject to some consistency conditions. They show explicitly how Halin graphs are included in the extension. Second, for recursively constructed graphs in general, the authors construct a predicate calculus within which graph problems can be stated and for those so stated, a linear time algorithm exists and can be automatically generated. They discuss some issues related to practical automatic generation.