On the Planarity of Jump Graphs
For a graph $G$ of size $m \geq 1$ and
edge-induced subgraphs $F$ and $H$ of size $k$ ($1 \leq k \leq m$),
the subgraph $H$ is said to be obtained from $F$ by an edge jump
if there exist four distinct vertices $u, v, w,$ and $x$ in $G$ such that
$uv \in E(F)$, $wx \in E(G) - E(F)$,
and $H = F - uv + wx$. The minimum number of edge jumps required to
transform $F$ into
$H$ is the $k$-jump distance from $F$ to $H$.
For a graph $G$ of size $m \geq 1$ and an integer $k$ with
$1 \leq k \leq m$, the
$k$-jump graph $J_k(G)$ is that graph whose vertices correspond to the
edge-induced subgraphs of size $k$ of $G$ and where two vertices of $J_k(G)$
are
adjacent if and only if the $k$-jump distance between the corresponding
subgraphs is 1. All
connected graphs $G$ for which $J_2(G)$ is planar are determined.