Analysis of cactus graphs using automata: properties and recognition time

This paper is devoted to the study of using automata with erasable colors to determine whether an arbitrary connected plane simple undirected graph is a cactus. An algorithm is given for determining this property, as well as lower and upper bounds of the number of steps that the automaton must take to complete the traversal.