  This paper studies infinite graphs produced from a natural unfolding
operation applied to finite graphs. Graphs produced via such operations are of
finite degree and automatic over the unary alphabet (that is, they can be
described by finite automata over unary alphabet). We investigate algorithmic
properties of such unfolded graphs given their finite presentations. In
particular, we ask whether a given node belongs to an infinite component,
whether two given nodes in the graph are reachable from one another, and
whether the graph is connected. We give polynomial-time algorithms for each of
these questions. For a fixed input graph, the algorithm for the first question
is in constant time and the second question is decided using an automaton that
recognizes the reachability relation in a uniform way. Hence, we improve on
previous work, in which non-elementary or non-uniform algorithms were found.
