A Separator Theorem for String Graphs and Its Applications
From MaRDI portal
Publication:3605480
DOI10.1007/978-3-642-00202-1_1zbMATH Open1211.05066OpenAlexW2170077534MaRDI QIDQ3605480FDOQ3605480
Authors: Jacob Fox, János Pach 
Publication date: 24 February 2009
Published in: WALCOM: Algorithms and Computation (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-642-00202-1_1
Recommendations
Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Connectivity (05C40)
Cites Work
- Generalized Nested Dissection
- Title not available (Why is that?)
- 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?)
- Title not available (Why is that?)
- A bipartite analogue of Dilworth's theorem
- The discharging method in combinatorial geometry and the Pach-Sharir conjecture
- 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
- Separators for sphere-packings and nearest neighbor graphs
- 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
- Coloring k k -free intersection graphs of geometric objects in the plane
- Intersection patterns of curves
- Title not available (Why is that?)
- Turán-type results for partial orders and intersection graphs of convex sets
- Girth in graphs
- Title not available (Why is that?)
- String graphs and incomparability graphs
- Topological graphs with no large grids
- Bandwidth, treewidth, separators, expansion, and universality
Cited In (14)
- Separators in region intersection graphs
- String graphs and incomparability graphs
- String graphs and incomparability graphs
- Separator theorems and Turán-type results for planar intersection graphs
- Minimal change list for Lucas strings and some graph theoretic consequences
- A separator theorem for string graphs and its applications
- Applications of a new separator theorem for string graphs
- Near-optimal separators in string graphs
- String graphs and separators
- A sharp threshold phenomenon in string graphs
- Almost all string graphs are intersection graphs of plane convex sets
- On well-connected sets of strings
- Title not available (Why is that?)
- 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 Q3605480)
