  The mobile robot dispersion problem on graphs asks $k\leq n$ robots placed
initially arbitrarily on the nodes of an $n$-node anonymous graph to reposition
autonomously to reach a configuration in which each robot is on a distinct node
of the graph. This problem is of significant interest due to its relationship
to other fundamental robot coordination problems, such as exploration,
scattering, load balancing, and relocation of self-driven electric cars
(robots) to recharge stations (nodes). In this paper, we provide two novel
deterministic algorithms for dispersion, one for arbitrary graphs and another
for grid graphs, in a synchronous setting where all robots perform their
actions in every time step. Our algorithm for arbitrary graphs has
$O(\min(m,k\Delta) \cdot \log k)$ steps runtime using $O(\log n)$ bits of
memory at each robot, where $m$ is the number of edges and $\Delta$ is the
maximum degree of the graph. This is an exponential improvement over the
$O(mk)$ steps best previously known algorithm. In particular, the runtime of
our algorithm is optimal (up to a $O(\log k)$ factor) in constant-degree
arbitrary graphs. Our algorithm for grid graphs has $O(\min(k,\sqrt{n}))$ steps
runtime using $\Theta(\log k)$ bits at each robot. This is the first algorithm
for dispersion in grid graphs. Moreover, this algorithm is optimal for both
memory and time when $k=\Omega(n)$.
