Time and space optimality of rotor-router graph exploration

We consider the problem of exploration of an anonymous, port-labeled, undirected graph with n nodes, m edges and diameter D, by a single mobile agent. Initially the agent does not know the graph topology nor any of the global parameters. Moreover, the agent does not know the incoming port when entering a vertex. Each vertex is endowed with memory that can be read and modified by the agent upon its visit to that node. However the agent has no operational memory i.e., it cannot carry any state while traversing an edge. In such a model at least log2⁡d bits are needed at each vertex of degree d for the agent to be able to traverse each graph edge. This number of bits is always sufficient to explore any graph in time O(mD) using algorithm Rotor-Router Yanovski et al. (2003) [1]. We show that even if the available node memory is unlimited then time Ω(mD) is required in some graphs, regardless of the algorithm. This shows that Rotor-Router is asymptotically optimal in the worst-case. Secondly we show that for the case of paths, Rotor-Router attains exactly optimal time.