Applications of a New Separator Theorem for String Graphs
From MaRDI portal
Publication:5414146
DOI10.1017/S0963548313000412zbMath1287.05066arXiv1302.7228MaRDI 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
05C35: Extremal problems in graph theory
52C10: Erd?s problems and related topics of discrete geometry
05C62: Graph representations (geometric and intersection representations, etc.)
Related Items
Orthogonal Tree Decompositions of Graphs, Separators in region intersection graphs, The Effect of Planarization on Width, Quantitative Restrictions on Crossing Patterns, Quasi-planar Graphs, Hasse diagrams with large chromatic number, Two-Planar Graphs Are Quasiplanar, Outerstring Graphs are $\chi$-Bounded, Decomposition of Multiple Packings with Subquadratic Union Complexity, Near-Optimal Separators in String Graphs, Optimality program in segment and string graphs, Quasiplanar graphs, string graphs, and the Erdős-Gallai problem, Grounded \(\mathrm{L}\)-graphs are polynomially \(\chi \)-bounded, Ramsey properties of semilinear graphs, Graph product structure for non-minor-closed classes, Coloring triangle-free L-graphs with \(O (\log \log n)\) colors, String graphs have the Erdős-Hajnal property, Coloring lines and Delaunay graphs with respect to boxes, On the Zarankiewicz problem for intersection hypergraphs, Zarankiewicz's problem for semi-algebraic hypergraphs, On-line approach to off-line coloring problems on graphs with geometric representations, New bounds on the maximum number of edges in \(k\)-quasi-planar graphs, Conflict-free coloring of string graphs, Planar point sets determine many pairwise crossing segments, Notes on graph product structure theory, A sharp threshold phenomenon in string graphs, Characterization of 2-path signed network, Coloring triangle-free rectangle overlap graphs with \(O(\log \log n)\) colors, Coloring curves that cross a fixed curve, Degeneracy of \(P_t\)-free and \(C_{\geq t}\)-free graphs with no large complete bipartite subgraphs, On the Size of Planarly Connected Crossing Graphs, On String Graph Limits and the Structure of a Typical String Graph
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
