2025/03/02 by Dibyayan Chakraborty, Chakraborty, Dibyayan
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #Computational Geometry and Mesh Generation #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Graph theory and applications
paper · pdf · doi:10.48550/arxiv.2503.00798
openalex publication_date 2025/03/02 · openalex created_date 2025/10/12 · openalex updated_date 2026/07/28
A graph H is an induced minor of a graph G if H can be obtained from G by a sequence of edge contractions and vertex deletions. Otherwise, G is H-induced minor-free. In this paper, we provide a different proof of the fact that K2,3-induced minor-free graphs admit a quasi-isometry with additive distortion to graphs with tree-width at most two. Our proof yields a O(nm)-time algorithm which takes as input a K2,3-induced minor-free graph with n vertices and m edges, and outputs a tree-width two graph H with the desired additive distortion. For universally signable graphs, a subclass of K2,3-induced minor-free graphs, the time complexity of our algorithm is linear. As a consequence, we obtain a truly sub-quadratic time additive constant factor approximation algorithm to compute the diameter of a universally signable graph. In contrast, assuming the Strong Exponential Time Hypothesis (SETH), the diameter of split graphs (a very restricted class of universally signable graphs), cannot be computed in truly sub-quadratic time [Borassi et al. (ENTCS, 2016)].