Mutual Witness Gabriel Drawings of Complete Bipartite Graphs

Let $\mathrm{\Gamma }$ be a straight-line drawing of a graph and let $u$ and $v$ be two vertices of $\mathrm{\Gamma }$. The Gabriel disk of $u,v$ is the disk having $u$ and $v$ as antipodal points. A pair $⟨{\mathrm{\Gamma }}_0,{\mathrm{\Gamma }}_1⟩$ of vertex-disjoint straight-line drawings form a mutual witness Gabriel drawing when, for $i=0,1$, any two vertices $u$ and $v$ of ${\mathrm{\Gamma }}_i$ are adjacent if and only if their Gabriel disk does not contain any vertex of ${\mathrm{\Gamma }}_{1-i}$. We characterize the pairs $⟨G_0,G_1⟩$ of complete bipartite graphs that admit a mutual witness Gabriel drawing. The characterization leads to a linear time testing algorithm. We also show that when at least one of the graphs in the pair $⟨G_0,G_1⟩$ is complete $k$-partite with $k>2$ and all partition sets in the two graphs have size greater than one, the pair does not admit a mutual witness Gabriel drawing.