A separator theorem for string graphs and its applications
From MaRDI portal
Publication:3058296
DOI10.1017/S0963548309990459zbMATH Open1230.05186MaRDI QIDQ3058296FDOQ3058296
Authors: Jacob Fox, János Pach 
Publication date: 19 November 2010
Published in: Combinatorics, Probability and Computing (Search for Journal in Brave)
Recommendations
Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Planar graphs; geometric and topological aspects of graph theory (05C10) Connectivity (05C40)
Cites Work
- Generalized Nested Dissection
- Graph Theory and Probability
- Applications of a Planar Separator Theorem
- Induced subdivisions in \(K_{s,s}\)-free graphs of large average degree
- Title not available (Why is that?)
- A bipartite analogue of Dilworth's theorem
- On planar intersection graphs with forbidden subgraphs
- A Separator Theorem for Planar Graphs
- A Separator Theorem for Nonplanar Graphs
- Separator theorems and Turán-type results for planar intersection graphs
- Intersection graphs of segments
- Random planar graphs
- Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms
- Separators for sphere-packings and nearest neighbor graphs
- Proper minor-closed families are small
- Coloring relatives of intervals on the plane. I: Chromatic number versus girth
- A separator theorem for graphs of bounded genus
- A Turán-type theorem on chords of a convex polygon
- Crossing number, pair-crossing number, and expansion
- Applications of the crossing number
- Girth in graphs
- Which crossing number is it anyway?
- Topological graphs with no large grids
- Bandwidth, treewidth, separators, expansion, and universality
Cited In (37)
- Separators in region intersection graphs
- Quasiplanar graphs, string graphs, and the Erdős-Gallai problem
- String graphs and incomparability graphs
- Coloring intersection graphs of arc-connected sets in the plane
- On the Zarankiewicz problem for intersection hypergraphs
- On grids in topological graphs
- Orthogonal tree decompositions of graphs
- Maximum independent set in 2-direction outersegment graphs
- Graph product structure for non-minor-closed classes
- Decomposition of Multiple Packings with Subquadratic Union Complexity
- A note on circular chromatic number of graphs with large girth and similar problems
- Zarankiewicz's problem for semi-algebraic hypergraphs
- The effect of planarization on width
- Conflict-free coloring of string graphs
- Subexponential algorithms for variants of the homomorphism problem in string graphs
- Separator theorems and Turán-type results for planar intersection graphs
- Clustered coloring of graphs with bounded layered treewidth and bounded degree
- Minimal change list for Lucas strings and some graph theoretic consequences
- A crossing lemma for Jordan curves
- Acyclic subgraphs of planar digraphs
- Applications of a new separator theorem for string graphs
- Near-optimal separators in string graphs
- String graphs have the Erdős-Hajnal property
- String graphs and separators
- On the size of outer-string representations
- On string graph limits and the structure of a typical string graph
- Ramsey numbers of cubes versus cliques
- Quasiplanar graphs, string graphs, and the Erdős-Gallai problem
- A sharp threshold phenomenon in string graphs
- Almost all string graphs are intersection graphs of plane convex sets
- Notes on graph product structure theory
- A Separator Theorem for String Graphs and Its Applications
- Outerstring graphs are \(\chi \)-bounded
- On well-connected sets of strings
- Many touchings force many crossings
- Many touchings force many crossings
- Almost all string graphs are intersection graphs of plane convex sets
This page was built for publication: A separator theorem for string graphs and its applications
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3058296)
