Abstract
Let be a straight-line drawing of a graph and let and be two vertices of . The Gabriel disk of is the disk having and as antipodal points. A pair of vertex-disjoint straight-line drawings form a mutual witness Gabriel drawing when, for , any two vertices and of are adjacent if and only if their Gabriel disk does not contain any vertex of . We characterize the pairs 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 is complete -partite with and all partition sets in the two graphs have size greater than one, the pair does not admit a mutual witness Gabriel drawing.
Connections
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 review
No reviews yet.
Discussion 0
Add a comment
No comments yet.