2023/11/25 by Haase, Carolina, Kindermann, Philipp
#Computational Geometry (cs.CG) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2311.15057
A pair ⟨ G0, G1 ⟩ of graphs admits a mutual witness proximity drawing ⟨ Γ0, Γ1 ⟩ when: (i) Γi represents Gi, and (ii) there is an edge (u,v) in Γi if and only if there is no vertex w in Γ1-i that is ``too close'' to both u and v (i=0,1). In this paper, we consider infinitely many definitions of closeness by adopting the β-proximity rule for any β∈ [1,∞] and study pairs of isomorphic trees that admit a mutual witness β-proximity drawing. Specifically, we show that every two isomorphic trees admit a mutual witness β-proximity drawing for any β∈ [1,∞]. The constructive technique can be made ``robust'': For some tree pairs we can suitably prune linearly many leaves from one of the two trees and still retain their mutual witness β-proximity drawability. Notably, in the special case of isomorphic caterpillars and β=1, we construct linearly separable mutual witness Gabriel drawings.