Mutual Witness Proximity Drawings of Isomorphic Trees

Abstract

A pair $⟨G_0,G_1⟩$ of graphs admits a mutual witness proximity drawing $⟨{\Gamma }_0,{\Gamma }_1⟩$ when: (i) ${\Gamma }_i$ represents $G_i$, and (ii) there is an edge $(u,v)$ in ${\Gamma }_i$ if and only if there is no vertex $w$ in ${\Gamma }_{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 $\beta$-proximity rule for any $\beta \in [1,\infty ]$ and study pairs of isomorphic trees that admit a mutual witness $\beta$-proximity drawing. Specifically, we show that every two isomorphic trees admit a mutual witness $\beta$-proximity drawing for any $\beta \in [1,\infty ]$. 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 $\beta$-proximity drawability. Notably, in the special case of isomorphic caterpillars and $\beta =1$, we construct linearly separable mutual witness Gabriel drawings.

Appears in the Proceedings of the 31st International Symposium on Graph Drawing and Network Visualization (GD 2023)