A Separator Theorem for String Graphs and Its Applications

DOI10.1007/978-3-642-00202-1_1MaRDI QIDQ3605480zbMATH OpenOpenAlexFDO

Authors Jacob Fox, János Pach

Publication date 24 February 2009

Published in WALCOM: Algorithms and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-00202-1_1

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Connectivity (05C40)

Recommendations

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

Cites work

• scientific article; zbMATH DE number 4142090 (Why is no real title available?)
• scientific article; zbMATH DE number 3919830 (Why is no real title available?)
• scientific article; zbMATH DE number 1179517 (Why is no real title available?)
• scientific article; zbMATH DE number 1518742 (Why is no real title available?)
• scientific article; zbMATH DE number 5035595 (Why is no real title available?)
• A Separator Theorem for Nonplanar Graphs
• A Separator Theorem for Planar Graphs
• A Turán-type theorem on chords of a convex polygon
• A bipartite analogue of Dilworth's theorem
• A separator theorem for graphs of bounded genus
• Applications of a Planar Separator Theorem
• Bandwidth, treewidth, separators, expansion, and universality
• Coloring k _k -free intersection graphs of geometric objects in the plane
• Coloring relatives of intervals on the plane. I: Chromatic number versus girth
• Crossing number, pair-crossing number, and expansion
• Generalized Nested Dissection
• Girth in graphs
• Graph Theory and Probability
• Induced subdivisions in \(K_{s,s}\)-free graphs of large average degree
• Intersection graphs of segments
• Intersection patterns of curves
• On planar intersection graphs with forbidden subgraphs
• Separator theorems and Turán-type results for planar intersection graphs
• Separators for sphere-packings and nearest neighbor graphs
• String graphs and incomparability graphs
• The discharging method in combinatorial geometry and the Pach-Sharir conjecture
• Topological graphs with no large grids
• Turán-type results for partial orders and intersection graphs of convex sets

Cited in

(14)

• Almost all string graphs are intersection graphs of plane convex sets
• Separators in region intersection graphs
• String graphs and incomparability graphs
• String graphs and incomparability graphs
• Separator theorems and Turán-type results for planar intersection graphs
• Minimal change list for Lucas strings and some graph theoretic consequences
• A separator theorem for string graphs and its applications
• Applications of a new separator theorem for string graphs
• Near-optimal separators in string graphs
• String graphs and separators
• A sharp threshold phenomenon in string graphs
• Almost all string graphs are intersection graphs of plane convex sets
• On well-connected sets of strings
• scientific article; zbMATH DE number 3981198 (Why is no real title available?)

This page was built for publication: A Separator Theorem for String Graphs and Its Applications

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