1. Mutual witness Gabriel drawings of complete bipartite graphs.
- Author
-
Lenhart, William J. and Liotta, Giuseppe
- Subjects
- *
BIPARTITE graphs , *COMPLETE graphs , *WITNESSES , *LEAD time (Supply chain management) - Abstract
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 forms 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 〈 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 the pair 〈 G 0 , G 1 〉 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 〈 K 2 , 2 , K 2 , 2 〉. [ABSTRACT FROM AUTHOR]
- Published
- 2023
- Full Text
- View/download PDF