Near-Optimal Separators in String Graphs

DOI10.1017/S0963548313000400zbMath1287.05094arXiv1302.6482MaRDI QIDQ5414151

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)

Related Items

Approximation Algorithms for Polynomial-Expansion and Low-Density Graphs ⋮ A crossing lemma for Jordan curves ⋮ Approximation Algorithms for Polynomial-Expansion and Low-Density Graphs ⋮ Degeneracy of \(P_t\)-free and \(C_{\geq t}\)-free graphs with no large complete bipartite subgraphs ⋮ Coloring curves that cross a fixed curve ⋮ Clique-based separators for geometric intersection graphs ⋮ String graphs have the Erdős-Hajnal property ⋮ On String Graph Limits and the Structure of a Typical String Graph ⋮ Refining the hierarchies of classes of geometric intersection graphs ⋮ Computing exact solutions of consensus halving and the Borsuk-Ulam theorem ⋮ Orthogonal Tree Decompositions of Graphs ⋮ Conflict-free coloring of string graphs ⋮ Optimality program in segment and string graphs ⋮ The Effect of Planarization on Width ⋮ Balanced line separators of unit disk graphs ⋮ Subexponential algorithms for variants of the homomorphism problem in string graphs ⋮ A sharp threshold phenomenon in string graphs ⋮ Separators in region intersection graphs ⋮ Outerstring Graphs are $\chi$-Bounded

Cites Work

• 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?
• Crossing number, pair-crossing number, and expansion
• A Separator Theorem for String Graphs and its Applications
• Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms
• Improved Approximation Algorithms for Minimum Weight Vertex Separators
• Applications of a New Separator Theorem for String Graphs

This page was built for publication: Near-Optimal Separators in String Graphs