Near-optimal separators in string graphs

2013/02/26 by Jiri Matousek, Matousek, Jiri · 6 citations
Computer Science · Mathematics · #05C10 #05C62 #Combinatorics (math.CO) #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #cs.DM #cs.DS #math.CO #msc:05C10 #msc:05C62

paper · pdf · doi:10.48550/arxiv.1302.6482

4 pages; minor corrections and updates compared to version 1

arxiv created 2013/05/06 · arxiv updated 2013/05/07

Abstract

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√(log m)) vertices, and they conjectured that the bound of O(√ m) actually holds. We obtain separators with O(√ m log m) vertices.

Cited by

• String Graphs: Product Structure and Localised Representations
• Star-Based Separators for Intersection Graphs of c-Colored Pseudo-Segments
• String graphs are quasi-isometric to planar graphs
• Burling graphs in graphs with large chromatic number
• C₄-free subgraphs of high degree with geometric applications
• Pushing the frontiers of subexponential FPT time for Feedback Vertex Set

Related

• Applications of a new separator theorem for string graphs
• String graphs and separators
• Separators in region intersection graphs
• Almost all string graphs are intersection graphs of plane convex sets
• String Graphs: Product Structure and Localised Representations