Anzeige
Erschienen in:
2014 | OriginalPaper | Buchkapitel
String graphs and separators
verfasst von : Jiří Matoušek
Erschienen in: Geometry, Structure and Randomness in Combinatorics
Verlag: Scuola Normale Superiore
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
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 pair-crossing number. For the existence of small separators, the proof includes generally useful results on approximate flow-cut dualities.