Mutual witness Gabriel drawings of complete bipartite graphs

Let r 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 (P0, P1) of vertex-disjoint straight-line drawings forms a mutual witness Gabriel drawing when, for i = 0, 1, any two vertices u and v of ri are adjacent if and only if their Gabriel disk does not contain any vertex of Gamma 1_i. We characterize the pairs (G0, G1) 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 the pair (G0, G1) consists of two complete multi-partite graphs whose partition sets all have size greater than one, then the pair does not admit a mutual witness Gabriel drawing unless the pair is (K2,2, K2,2). (c) 2023 The Author(s). Published by Elsevier B.V. This is an open access article under the CC BY license (http://creativecommons .org /licenses /by /4 .0/).