Generic algorithms for some decision problems on fasciagraphs and rotagraphs

A fasciagraph consists of a sequence of copies of the same graph, each copy being linked to the next one according to a regular scheme. More precisely, a fasciagraph is characterized by an integer nn (the number of copies or fibers) and a mixed graph MM. In a rotagraph, the last copy is also linked to the first one. In the literature, similar methods were used to address various problems on rotagraphs and fasciagraphs. The goal of our work is to define a class of decision problems for which this kind of method works. For this purpose, we introduce the notion of pseudo-dd-local qq-properties of fasciagraphs and rotagraphs. For a mixed graph MM and a pseudo-dd-local qq-property PP, we propose a generic algorithm for rotagraphs (respectively, fasciagraphs) that computes in one run the data that allow one to decide, for any integer n≥dn≥d (respectively, n≥d+2n≥d+2), whether the rotagraph (respectively, fasciagraph) of length nn based on MM satisfies PP, using only a small number of elementary operations independent of nn.