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.