  In this paper, we study isogeny graphs of supersingular elliptic curves.
Supersingular isogeny graphs were introduced as a hard problem into
cryptography by Charles, Goren, and Lauter for the construction of
cryptographic hash functions [CGL06]. These are large expander graphs, and the
hard problem is to find an efficient algorithm for routing, or path-finding,
between two vertices of the graph. We consider four aspects of supersingular
isogeny graphs, study each thoroughly and, where appropriate, discuss how they
relate to one another.
  First, we consider two related graphs that help us understand the structure:
the `spine' $\mathcal{S}$, which is the subgraph of
$\mathcal{G}_\ell(\overline{\mathbb{F}_p})$ given by the $j$-invariants in
$\mathbb{F}_p$, and the graph $\mathcal{G}_\ell(\mathbb{F}_p)$, in which both
curves and isogenies must be defined over $\mathbb{F}_p$. We show how to pass
from the latter to the former. The graph $\mathcal{S}$ is relevant for
cryptanalysis because routing between vertices in $\mathbb{F}_p$ is easier than
in the full isogeny graph. The $\mathbb{F}_p$-vertices are typically assumed to
be randomly distributed in the graph, which is far from true. We provide an
analysis of the distances of connected components of $\mathcal{S}$.
  Next, we study the involution on $\mathcal{G}_\ell(\overline{\mathbb{F}_p})$
that is given by the Frobenius of $\mathbb{F}_p$ and give heuristics on how
often shortest paths between two conjugate $j$-invariants are preserved by this
involution (mirror paths). We also study the related question of what
proportion of conjugate $j$-invariants are $\ell$-isogenous for $\ell = 2,3$.
We conclude with experimental data on the diameters of supersingular isogeny
graphs when $\ell = 2$ and compare this with previous results on diameters of
LPS graphs and random Ramanujan graphs.
