A separator theorem for string graphs and its applications
From MaRDI portal
Recommendations
Cites work
- A bipartite analogue of Dilworth's theorem
- A separator theorem for graphs of bounded genus
- A Separator Theorem for Nonplanar Graphs
- A Separator Theorem for Planar Graphs
- A Turán-type theorem on chords of a convex polygon
- Applications of a Planar Separator Theorem
- Applications of the crossing number
- Bandwidth, treewidth, separators, expansion, and universality
- Coloring relatives of intervals on the plane. I: Chromatic number versus girth
- Crossing number, pair-crossing number, and expansion
- Generalized Nested Dissection
- Girth in graphs
- Graph Theory and Probability
- scientific article; zbMATH DE number 3919830 (Why is no real title available?)
- Induced subdivisions in \(K_{s,s}\)-free graphs of large average degree
- Intersection graphs of segments
- Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms
- On planar intersection graphs with forbidden subgraphs
- Proper minor-closed families are small
- Random planar graphs
- Separator theorems and Turán-type results for planar intersection graphs
- Separators for sphere-packings and nearest neighbor graphs
- Topological graphs with no large grids
- Which crossing number is it anyway?
Cited in
(47)- A crossing lemma for Jordan curves
- Conflict-free coloring of string graphs
- Notes on graph product structure theory
- A sharp threshold phenomenon in string graphs
- On well-connected sets of strings
- Almost all string graphs are intersection graphs of plane convex sets
- 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
- Minimal change list for Lucas strings and some graph theoretic consequences
- On the Zarankiewicz problem for intersection hypergraphs
- On string graph limits and the structure of a typical string graph
- Maximum independent set in 2-direction outersegment graphs
- String graphs and separators
- A note on circular chromatic number of graphs with large girth and similar problems
- A Separator Theorem for String Graphs and Its Applications
- Many touchings force many crossings
- Orthogonal tree decompositions of graphs
- Separators in region intersection graphs
- Coloring intersection graphs of arc-connected sets in the plane
- The effect of planarization on width
- On the size of outer-string representations
- Almost all string graphs are intersection graphs of plane convex sets
- Ramsey numbers of cubes versus cliques
- Outerstring graphs are -bounded
- Decomposition of Multiple Packings with Subquadratic Union Complexity
- Applications of a new separator theorem for string graphs
- Near-optimal separators in string graphs
- String graphs and incomparability graphs
- 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
- Quasiplanar graphs, string graphs, and the Erdős-Gallai problem
- Clustered coloring of graphs with bounded layered treewidth and bounded degree
- Recognition and proper coloring of unit segment intersection graphs
- A structure theorem for pseudo-segments and its applications
- A survey of degree-boundedness
- A structure theorem for pseudosegments and its applications
- Powers of planar graphs, product structure, and blocking partitions
- Pair crossing number, cutwidth, and good drawings on arbitrary point sets
- Zarankiewicz's problem for semi-algebraic hypergraphs
- Sparse outerstring graphs have logarithmic treewidth
- Combinatorics. Abstracts from the workshop held January 4--9, 2026
- Strongly sublinear separators and bounded asymptotic dimension for sphere intersection graphs
- On geometric bipartite graphs with asymptotically smallest Zarankiewicz numbers
- Separator theorems and Turán-type results for planar intersection graphs
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)
