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)
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
Applications of a New Separator Theorem for String Graphs, Near-Optimal Separators in String Graphs, Coloring intersection graphs of arc-connected sets in the plane, On grids in topological graphs, Maximum Independent Set in 2-Direction Outersegment Graphs
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
