Separator theorems and Turán-type results for planar intersection graphs

DOI10.1016/j.aim.2008.06.002zbMath1148.05050OpenAlexW2034834286MaRDI QIDQ947779

Jacob Fox, János Pach

Publication date: 7 October 2008

Published in: Advances in Mathematics (Search for Journal in Brave)

Full work available at URL: http://infoscience.epfl.ch/record/129257

zbMATH Keywords

intersection graphcombinatorial geometryplanarextremal graph theorygraph separators

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Planar graphs; geometric and topological aspects of graph theory (05C10) Convex sets in (2) dimensions (including convex curves) (52A10) Graph theory (05C99) Curves in Euclidean and related spaces (53A04)

Related Items

On the Zarankiewicz problem for intersection hypergraphs, Turán-type results for intersection graphs of boxes, A crossing lemma for Jordan curves, Space-efficient algorithms for reachability in directed geometric graphs, Coloring \(K_{k}\)-free intersection graphs of geometric objects in the plane, Quasiplanar graphs, string graphs, and the Erdős-Gallai problem, String graphs have the Erdős-Hajnal property, Orthogonal Tree Decompositions of Graphs, Reachability problems for transmission graphs, Zarankiewicz’s problem for semilinear hypergraphs, Extremal even-cycle-free subgraphs of the complete transposition graphs, Box and Segment Intersection Graphs with Large Girth and Chromatic Number, Applications of a New Separator Theorem for String Graphs, Near-Optimal Separators in String Graphs, Reachability problems for transmission graphs, Zarankiewicz's problem for semi-algebraic hypergraphs, A Separator Theorem for String Graphs and its Applications, A Separator Theorem for String Graphs and Its Applications, Planar point sets determine many pairwise crossing segments, Balanced line separators of unit disk graphs, Unnamed Item

Cites Work

• A Turán-type theorem on chords of a convex polygon
• A separator theorem for graphs of bounded genus
• On planar intersection graphs with forbidden subgraphs
• Generalized Nested Dissection
• A Separator Theorem for Nonplanar Graphs
• Separators for sphere-packings and nearest neighbor graphs
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item