2022/09/02 by Lenhart, William J., Liotta, Giuseppe · 1 citation
#Computational Geometry (cs.CG) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2209.01004
Let Γ be a straight-line drawing of a graph and let u and v be two vertices of Γ. The Gabriel disk of u,v is the disk having u and v as antipodal points. A pair ⟨ Γ0,Γ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 Γi are adjacent if and only if their Gabriel disk does not contain any vertex of Γ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 at least one of the graphs in the pair ⟨ G0, G1 ⟩ 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.