  We investigate two fundamental problems in mobile computing: exploration and
rendezvous, with two distinct mobile agents in an unknown graph. The agents may
communicate by reading and writing information on whiteboards that are located
at all nodes. They both move along one adjacent edge at every time-step. In the
exploration problem, the agents start from the same arbitrary node and must
traverse all the edges. We present an algorithm achieving collective
exploration in $m$ time-steps, where $m$ is the number of edges of the graph.
This improves over the guarantee of depth-first search, which requires $2m$
time-steps. In the rendezvous problem, the agents start from different nodes of
the graph and must meet as fast as possible. We present an algorithm
guaranteeing rendezvous in at most $\frac{3}{2}m$ time-steps. This improves
over the so-called `wait for Mommy' algorithm which is based on depth-first
search and which also requires $2m$ time-steps. Importantly, all our guarantees
are derived from a more general asynchronous setting in which the speeds of the
agents are controlled by an adversary at all times. Our guarantees generalize
to weighted graphs, when replacing the number of edges $m$ with the sum of all
edge lengths. We show that our guarantees are met with matching lower-bounds in
the asynchronous setting.
