A Separator Theorem for String Graphs and its Applications

DOI10.1017/S0963548309990459zbMath1230.05186MaRDI QIDQ3058296

János Pach, Jacob Fox

Publication date: 19 November 2010

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

zbMATH Keywords

intersection graph; string graph; locally tree-like string graphs

Mathematics Subject Classification ID

68R10: Graph theory (including graph drawing) in computer science

68U05: Computer graphics; computational geometry (digital and algorithmic aspects)

05C10: Planar graphs; geometric and topological aspects of graph theory

05C40: Connectivity

Related Items

Many Touchings Force Many Crossings, Orthogonal Tree Decompositions of Graphs, Separators in region intersection graphs, The Effect of Planarization on Width, Outerstring Graphs are $\chi$-Bounded, Decomposition of Multiple Packings with Subquadratic Union Complexity, Applications of a New Separator Theorem for String Graphs, Near-Optimal Separators in String Graphs, On the Zarankiewicz problem for intersection hypergraphs, Coloring intersection graphs of arc-connected sets in the plane, Ramsey numbers of cubes versus cliques, Zarankiewicz's problem for semi-algebraic hypergraphs, A crossing lemma for Jordan curves, On grids in topological graphs, Subexponential algorithms for variants of the homomorphism problem in string graphs, Many touchings force many crossings, Acyclic subgraphs of planar digraphs, Maximum Independent Set in 2-Direction Outersegment Graphs, A Note on Circular Chromatic Number of Graphs with Large Girth and Similar Problems

Cites Work

• Unnamed Item
• Induced subdivisions in \(K_{s,s}\)-free graphs of large average degree
• Girth in graphs
• A bipartite analogue of Dilworth's theorem
• Separator theorems and Turán-type results for planar intersection graphs
• A Turán-type theorem on chords of a convex polygon
• Intersection graphs of segments
• Coloring relatives of intervals on the plane. I: Chromatic number versus girth
• Random planar graphs
• Which crossing number is it anyway?
• Crossing number, pair-crossing number, and expansion
• Applications of the crossing number
• Proper minor-closed families are small
• Topological graphs with no large grids
• Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms
• A separator theorem for graphs of bounded genus
• Graph Theory and Probability
• On planar intersection graphs with forbidden subgraphs
• A Separator Theorem for Planar Graphs
• Generalized Nested Dissection
• Applications of a Planar Separator Theorem
• A Separator Theorem for Nonplanar Graphs
• Separators for sphere-packings and nearest neighbor graphs
• Bandwidth, treewidth, separators, expansion, and universality