$K_{2,3}$-induced minor-free graphs admit quasi-isometry with additive distortion to graphs of tree-width at most two
By: Dibyayan Chakraborty
Potential Business Impact:
Makes complex networks simpler to understand.
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 prove that $K_{2,3}$-induced minor-free graphs admit a quasi-isometry with additive distortion to graphs with tree-width at most two. Our result implies that a recent conjecture of Nguyen et al. [Coarse tree-width (2025)] holds for $K_{2,3}$-induced minor-free graphs.
Similar Papers
Excluding $K_{2,t}$ as a fat minor
Combinatorics
Helps computers measure how "stretched" graphs are.
Excluding a Forest Induced Minor
Combinatorics
Finds patterns in networks, even when parts are missing.
Induced Minors and Region Intersection Graphs
Combinatorics
Graphs can't always be drawn as overlapping shapes.