Mutual Witness Gabriel Drawings of Complete Bipartite Graphs

Abstract

Let $\Gamma$ be a straight-line drawing of a graph and let $u$ and $v$ be two vertices of $\Gamma$. The Gabriel disk of $u,v$ is the disk having $u$ and $v$ as antipodal points. A pair $⟨{\Gamma }_0,{\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 ${\Gamma }_i$ are adjacent if and only if their Gabriel disk does not contain any vertex of ${\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.

Appears in the Proceedings of the 30th International Symposium on Graph Drawing and Network Visualization (GD 2022)