Near-optimal separators in string graphs

DOI10.1017/S0963548313000400MaRDI QIDQ5414151zbMATH OpenFDO

Authors Jiří Matoušek

Publication date 2 May 2014

Published in Combinatorics, Probability and Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1302.6482

zbMATH Keywords

crossing numberpair-crossing number

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Graph representations (geometric and intersection representations, etc.) (05C62)

Abstract: Let G be a string graph (an intersection graph of continuous arcs in the plane) with m edges. Fox and Pach proved that G has a separator consisting of O(m^{3/4}sqrt{log m})$ vertices, and they conjectured that the bound of O(sqrt m) actually holds. We obtain separators with O(sqrt m log m) vertices.

Recommendations

• Separators in region intersection graphs
• A Separator Theorem for String Graphs and Its Applications
• A separator theorem for string graphs and its applications
• String graphs and separators
• Applications of a new separator theorem for string graphs

Cites work

• A separator theorem for string graphs and its applications
• Applications of a new separator theorem for string graphs
• Crossing number, pair-crossing number, and expansion
• Improved Approximation Algorithms for Minimum Weight Vertex Separators
• Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms
• On average distortion of embedding metrics into the line
• Separator theorems and Turán-type results for planar intersection graphs
• Which crossing number is it anyway?

Cited in

(32)

• A crossing lemma for Jordan curves
• Conflict-free coloring of string graphs
• A sharp threshold phenomenon in string graphs
• Computing exact solutions of consensus halving and the Borsuk-Ulam theorem
• Subexponential algorithms for variants of the homomorphism problem in string graphs
• Coloring curves that cross a fixed curve
• Degeneracy of \(P_t\)-free and \(C_{\geq t}\)-free graphs with no large complete bipartite subgraphs
• On string graph limits and the structure of a typical string graph
• A separator theorem for string graphs and its applications
• String graphs and separators
• Approximation Algorithms for Polynomial-Expansion and Low-Density Graphs
• A Separator Theorem for String Graphs and Its Applications
• Approximation algorithms for polynomial-expansion and low-density graphs
• Orthogonal tree decompositions of graphs
• Separators in region intersection graphs
• The effect of planarization on width
• Outerstring graphs are -bounded
• Applications of a new separator theorem for string graphs
• Refining the hierarchies of classes of geometric intersection graphs
• Balanced line separators of unit disk graphs
• Optimality program in segment and string graphs
• Clique-based separators for geometric intersection graphs
• String graphs have the Erdős-Hajnal property
• Recognition and proper coloring of unit segment intersection graphs
• A survey of degree-boundedness
• Powers of planar graphs, product structure, and blocking partitions
• Pair crossing number, cutwidth, and good drawings on arbitrary point sets
• Sparse outerstring graphs have logarithmic treewidth
• Shortest path separators in unit disk graphs
• Combinatorics. Abstracts from the workshop held January 4--9, 2026
• Strongly sublinear separators and bounded asymptotic dimension for sphere intersection graphs
• Pushing the frontiers of subexponential FPT time for feedback vertex set

This page was built for publication: Near-optimal separators in string graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5414151)