On the planarity of jump graphs (Q1567614)

Let \(G\) be a graph of size \(m\geq 1\) and let \(F\) and \(H\) be edge-induced subgraphs of \(G\) of size \(k\) with \(1\leq k\leq m\). In the literature is then defined 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 defined as a graph whose vertices correspond to the edge-induced subgraphs of size \(k\) of \(G\) and two of their vertices are adjacent if and only if the \(k\)-jump distance between the corresponding subgraphs is 1. The authors determine all connected graphs \(G\) for which \(J_2(G)\) is planar. This problem is a relatively hard problem.