Efficient periodic graph traversal on graphs with a given rotation system

We consider periodic graph traversal in anonymous undirected graphs by a finite state Mealy automaton (agent). The problem is to design an automaton A and a port labeling scheme L such that A (using L) performs on any undirected graph an infinite walk that periodically visit all vertices. The goal is to minimize the revisit time of any vertex over all graphs (traversal period) π. If the labeling scheme L is given by an adversary, it has been shown by Budach [6] that no such finite automaton A exists. If L does not need to be a permutation at every vertex, one can easily encode a spanning tree and A can perform traversal with period 2n − 2 even it is an oblivious agent. The problem is difficult when L is limited to be a permutation. The best known upper bound on the traversal period in such a case is 3.5n−2 by Czyzowicz et al. [11], where n is the number of vertices. It is an open problem whether it is possible to achieve traversal period of 2n − 2. In this thesis, we answer this question affirmatively under the assumption that the input graph G is given with a rotation system, where a rotation system, where a rotation system of a graph is given by lists of local orders of edges incident to each vertex the graph.