A Separator Theorem for String Graphs and its Applications
From MaRDI portal
Publication:3058296
DOI10.1017/S0963548309990459zbMath1230.05186MaRDI QIDQ3058296
Publication date: 19 November 2010
Published in: Combinatorics, Probability and Computing (Search for Journal in Brave)
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)
Related Items
On the Zarankiewicz problem for intersection hypergraphs, A crossing lemma for Jordan curves, A Note on Circular Chromatic Number of Graphs with Large Girth and Similar Problems, Quasiplanar graphs, string graphs, and the Erdős-Gallai problem, Graph product structure for non-minor-closed classes, String graphs have the Erdős-Hajnal property, Decomposition of Multiple Packings with Subquadratic Union Complexity, Coloring intersection graphs of arc-connected sets in the plane, Many Touchings Force Many Crossings, Orthogonal Tree Decompositions of Graphs, Ramsey numbers of cubes versus cliques, On grids in topological graphs, Applications of a New Separator Theorem for String Graphs, Near-Optimal Separators in String Graphs, Conflict-free coloring of string graphs, Zarankiewicz's problem for semi-algebraic hypergraphs, The Effect of Planarization on Width, Planar point sets determine many pairwise crossing segments, Acyclic subgraphs of planar digraphs, Unnamed Item, Subexponential algorithms for variants of the homomorphism problem in string graphs, Notes on graph product structure theory, Many touchings force many crossings, A sharp threshold phenomenon in string graphs, Maximum Independent Set in 2-Direction Outersegment Graphs, Separators in region intersection graphs, Outerstring Graphs are $\chi$-Bounded
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
