  We consider the problem of finding edge-disjoint paths between given pairs of
vertices in a sufficiently strong $d$-regular expander graph $G$ with $n$
vertices. In particular, we describe a deterministic, polynomial time algorithm
which maintains an initially empty collection of edge-disjoint paths $\mathcal
P$ in $G$ and fulfills any series of two types of requests:
  1. Given two vertices $a$ and $b$ such that each appears as an endpoint in
$O(d)$ paths in $\mathcal P$ and, additionally, $|\mathcal P| = O(n d / \log
n)$, the algorithm finds a path of length at most $\log n$ connecting $a$ and
$b$ which is edge-disjoint from all other paths in $\mathcal P$, and adds it to
$\mathcal P$.
  2. Remove a given path $P \in \mathcal{P}$ from $\mathcal{P}$.
  Importantly, each request is processed before seeing the next one. The upper
bound on the length of found paths and the constraints are the best possible up
to a constant factor. This establishes the first online algorithm for finding
edge-disjoint paths in expanders which also allows removals, significantly
strengthening a long list of previous results on the topic.
