Total: 1
Motivated by a question of Galby, Munaro, and Yang (SoCG 2023) asking whether every graph class of bounded layered tree-independence number admits clique-based separators of sublinear weight, we investigate relations between layered tree-independence number, weight of clique-based separators, clique cover degeneracy and independence degeneracy. In particular, we provide a number of results bounding these parameters on geometric intersection graphs. For example, we show that the layered tree-independence number is O(g) for g-map graphs, O(rtanhr) for hyperbolic uniform disk graphs with radius r, and O(1) for spherical uniform disk graphs with radius r. Our structural results have algorithmic consequences. In particular, we obtain a number of subexponential or quasi-polynomial-time algorithms for weighted problems such as \textsc{Max Weight Independent Set} and \textsc{Min Weight Feedback Vertex Set} on several geometric intersection graphs. Finally, we conjecture that every fractionally tree-independence-number-fragile graph class has bounded independence degeneracy.