String graphs and separators

DOI10.1007/978-88-7642-525-7_5MaRDI QIDQ3194867zbMATH OpenOpenAlexFDO

Authors Jiří Matoušek

Publication date 20 October 2015

Published in Geometry, Structure and Randomness in Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1311.5048

zbMATH Keywords

crossing number of a graphintersection graphs of curves in the planepair-crossing number

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10)

Abstract: String graphs, that is, intersection graphs of curves in the plane, have been studied since the 1960s. We provide an expository presentation of several results, including very recent ones: some string graphs require an exponential number of crossings in every string representation; exponential number is always sufficient; string graphs have small separators; and the current best bound on the crossing number of a graph in terms of the pair-crossing number. For the existence of small separators, unwrapping the complete proof include generally useful results on approximate flow-cut dualities.

Recommendations

• A Separator Theorem for String Graphs and Its Applications
• A separator theorem for string graphs and its applications
• Near-optimal separators in string graphs
• Separators in region intersection graphs
• Applications of a new separator theorem for string graphs

Cited in

(18)

• Separating strings with small automata
• String graphs requiring exponential representations
• String shuffle: circuits and graphs
• Bounds on the bend number of split and cocomparability graphs
• Border Array for Structural Strings
• A separator theorem for string graphs and its applications
• A Separator Theorem for String Graphs and Its Applications
• Orthogonal tree decompositions of graphs
• Separators in region intersection graphs
• Contraction-bidimensionality of geometric intersection graphs
• Near-optimal separators in string graphs
• String graphs and incomparability graphs
• Refining the hierarchies of classes of geometric intersection graphs
• Graphs of large chromatic number
• A survey of degree-boundedness
• Sparse outerstring graphs have logarithmic treewidth
• Pushing the frontiers of subexponential FPT time for feedback vertex set
• Contraction bidimensionality of geometric intersection graphs

This page was built for publication: String graphs and separators

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3194867)