Near-Optimal Separators in String Graphs

Let G be a string graph (an intersection graph of continuous arcs in the plane) with m edges. Fox and Pach proved that G has a separator consisting of $O(m^{3/4}\sqrt{\log m})$ vertices, and they conjectured that the bound of $O(\sqrt m)$ actually holds. We obtain separators with $O(\sqrt m \,\log m...

Full description

Saved in:
Bibliographic Details
Published in:Combinatorics, probability & computing probability & computing, 2014-01, Vol.23 (1), p.135-139
Main Author: MATOUSEK, JIRÃ
Format: Article
Language:English
Subjects:
Combinatorial analysis
Computation
Graphs
Intersections
Planes
Separators
Strings
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Let G be a string graph (an intersection graph of continuous arcs in the plane) with m edges. Fox and Pach proved that G has a separator consisting of $O(m^{3/4}\sqrt{\log m})$ vertices, and they conjectured that the bound of $O(\sqrt m)$ actually holds. We obtain separators with $O(\sqrt m \,\log m)$ vertices.
ISSN:0963-5483
1469-2163
DOI:10.1017/S0963548313000400