Mutual Witness Gabriel Drawings of Complete Bipartite Graphs

preprint2022arXivOpen access

Abstract

Let ΓΓ be a straight-line drawing of a graph and let uu and vv be two vertices of ΓΓ. The Gabriel disk of u,vu,v is the disk having uu and vv as antipodal points. A pair ⟨Γ0,Γ1⟩\langle Γ_0,Γ_1 \rangle of vertex-disjoint straight-line drawings form a mutual witness Gabriel drawing when, for i=0,1i=0,1, any two vertices uu and vv of ΓiΓ_i are adjacent if and only if their Gabriel disk does not contain any vertex of Γ1−iΓ_{1-i}. We characterize the pairs ⟨G0,G1⟩\langle G_0,G_1 \rangle 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⟩\langle G_0, G_1 \rangle is complete kk-partite with k>2k>2 and all partition sets in the two graphs have size greater than one, the pair does not admit a mutual witness Gabriel drawing.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.