论文标题
共同的见证人Gabriel图纸
Mutual Witness Gabriel Drawings of Complete Bipartite Graphs
论文作者
论文摘要
令$γ$为图的直线图，让$ u $，$ v $为两个顶点$γ$。 $ u，v $的Gabriel磁盘是具有$ u $和$ v $的磁盘作为反点数。一对$ \ langle的γ_0，γ_1\ rangle $ $ f tertex-dischoint直线图形构成共同的证人Gabriel绘图，何时，对于$ i = 0,1 $，任何两个顶点$ u $ u $ u $ u $ u $ u $ u $ u $ u $ u $ u $ u $的$umγ_i$仅在gabriel disk n. gabriel disk n.1 $ a $ a $ a $ a $ a $ a $ a $ a $ a $ n.我们表征了对$ \ langle g_0，g_1 \ rangle $的完整两部分图，该图允许共同的证人Gabriel绘图。表征导致线性时间测试算法。我们还表明，当对$ \ langle g_0中的至少一个图表，g_1 \ rangle $是完整的$ k $ - 零件，带有$ k> 2 $，并且两个图中的所有分区集都大于一个尺寸，这对不承认共同的证人Gabriel绘图。
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 $\langle Γ_0,Γ_1 \rangle$ 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 $\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 $\langle G_0, G_1 \rangle $ 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.
