Applications of a New Separator Theorem for String Graphs
From MaRDI portal
Publication:5414146
DOI10.1017/S0963548313000412zbMath1287.05066arXiv1302.7228OpenAlexW2109298068MaRDI QIDQ5414146
Publication date: 2 May 2014
Published in: Combinatorics, Probability and Computing (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1302.7228
Extremal problems in graph theory (05C35) Erd?s problems and related topics of discrete geometry (52C10) Graph representations (geometric and intersection representations, etc.) (05C62)
Related Items
On the Zarankiewicz problem for intersection hypergraphs, Degeneracy of \(P_t\)-free and \(C_{\geq t}\)-free graphs with no large complete bipartite subgraphs, Coloring curves that cross a fixed curve, Quasiplanar graphs, string graphs, and the Erdős-Gallai problem, Grounded \(\mathrm{L}\)-graphs are polynomially \(\chi \)-bounded, Ramsey properties of semilinear graphs, On the Size of Planarly Connected Crossing Graphs, Graph product structure for non-minor-closed classes, Coloring triangle-free L-graphs with \(O (\log \log n)\) colors, New bounds on the maximum number of edges in \(k\)-quasi-planar graphs, String graphs have the Erdős-Hajnal property, Coloring lines and Delaunay graphs with respect to boxes, Decomposition of Multiple Packings with Subquadratic Union Complexity, On String Graph Limits and the Structure of a Typical String Graph, Characterization of 2-path signed network, Orthogonal Tree Decompositions of Graphs, Near-Optimal Separators in String Graphs, Coloring triangle-free rectangle overlap graphs with \(O(\log \log n)\) colors, Two-Planar Graphs Are Quasiplanar, Conflict-free coloring of string graphs, Zarankiewicz's problem for semi-algebraic hypergraphs, On-line approach to off-line coloring problems on graphs with geometric representations, Optimality program in segment and string graphs, The Effect of Planarization on Width, Planar point sets determine many pairwise crossing segments, Notes on graph product structure theory, A sharp threshold phenomenon in string graphs, Separators in region intersection graphs, Outerstring Graphs are $\chi$-Bounded, Quantitative Restrictions on Crossing Patterns, Quasi-planar Graphs, Hasse diagrams with large chromatic number
Cites Work
- Coloring \(K_{k}\)-free intersection graphs of geometric objects in the plane
- Ramsey-type theorems
- A bipartite analogue of Dilworth's theorem
- Separator theorems and Turán-type results for planar intersection graphs
- A bipartite strengthening of the crossing Lemma
- On the maximum number of edges in topological graphs with no four pairwise crossing edges
- Quasi-planar graphs have a linear number of edges
- A Separator Theorem for String Graphs and its Applications
- Improved Approximation Algorithms for Minimum Weight Vertex Separators
- New lower bound techniques for VLSI
- String graphs and incomparability graphs
