Hostname: page-component-745bb68f8f-lrblm Total loading time: 0 Render date: 2025-02-06T16:17:26.246Z Has data issue: false hasContentIssue false
  • English
  • Français

Near-Optimal Separators in String Graphs

Published online by Cambridge University Press:  07 October 2013

JIŘÍ MATOUŠEK
JIŘÍ MATOUŠEK*
Affiliation:
Department of Applied Mathematics and Institute of Theoretical Computer Science (ITI), Charles University, Malostranské nám. 25, 11800 Praha 1, Czech Republic and Institute of Theoretical Computer Science, ETH Zurich, 8092 Zurich, Switzerland (e-mail: matousek@kam.mff.cuni.cz)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

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.

Keywords

Primary 05C62Secondary 05C10
Type
Paper
Information
Combinatorics, Probability and Computing , Volume 23 , Issue 1 , January 2014 , pp. 135 - 139
Copyright
Copyright © Cambridge University Press 2013 

References

[1]Biswal, P., Lee, J. R. and Rao, S. (2010) Eigenvalue bounds, spectral partitioning, and metrical deformations via flows. J. Assoc. Comput. Mach. 57 #13.Google Scholar
[2]Feige, U., Hajiaghayi, M. T. and Lee, J. R. (2008) Improved approximation algorithms for minimum weight vertex separators. SIAM J. Comput. 38 629–657.CrossRefGoogle Scholar
[3]Fox, J. and Pach, J. (2008) Separator theorems and Turán-type results for planar intersection graphs. Adv. Math. 219 1070–1080.CrossRefGoogle Scholar
[4]Fox, J. and Pach, J. (2010) A separator theorem for string graphs and its applications. Combin. Probab. Comput. 19 371–390.CrossRefGoogle Scholar
[5]Fox, J. and Pach, J. (2014) Applications of a new separator theorem for string graphs. Combin. Probab. Comput. 23 66–74.CrossRefGoogle Scholar
[6]Kolman, P. and Matoušek, J., J. (2004) Crossing number, pair-crossing number, and expansion. J. Combin. Theory Ser. B 92 99–113.Google Scholar
[7]Leighton, T. and Rao, S. (1999) Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms. J. Assoc. Comput. Mach. 46 787–832.CrossRefGoogle Scholar
[8]Pach, J. and Tóth, G. (2000) Which crossing number is it anyway? J. Combin. Theory Ser. B 80 225–246.CrossRefGoogle Scholar
[9]Rabinovich, Y. (2008) On average distortion of embedding metrics into the line. Discrete Comput. Geom. 39 720–733.Google Scholar
[10]Tóth, G. (2012) A better bound for pair-crossing number. In Thirty Essays on Geometric Graph Theory (Pach, J., ed.), Springer, pp. 563–567.Google Scholar