A Separator Theorem for String Graphs and its Applications

No abstract is available for this paper.

• Publication year

  2009

• Venue

  Combinatorics, probability & computing

• Publication date

  2009-02-18

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1017/S0963548309990459
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Computational Geometry

  2018cited by this paper
• The Probabilistic Method

  2015cited by this paper
• Intersection patterns of curves

  2011influential reference
• Turán-type results for partial orders and intersection graphs of convex sets

  2010cited by this paper
• Small graph classes and bounded expansion

  2010cited by this paper
• A bipartite analogue of Dilworth's theorem for multiple partial orders

  2009cited by this paper
• Bandwidth, treewidth, separators, expansion, and universality

  2008cited by this paper
• Labelings of graphs

  2008cited by this paper
• On planar intersection graphs with forbidden subgraphs

  2008cited by this paper
• Coloring kk-free intersection graphs of geometric objects in the plane

  2008influential reference
• Separator theorems and Turán-type results for planar intersection graphs

  2008influential reference
• Combinatorial Geometry

  2006cited by this paper
• A Bipartite Analogue of Dilworth’s Theorem

  2006cited by this paper
• Proper minor-closed families are small

  2006cited by this paper
• Comment on Fox news

  2006cited by this paper
• Topological Graphs with No Large Grids

  2005cited by this paper
• Random planar graphs

  2005cited by this paper
• Induced Subdivisions In Ks,s-Free Graphs of Large Average Degree

  2004cited by this paper
• The Probabilistic Method: Alon/Probabilistic Method

  2004cited by this paper
• Crossing number, pair-crossing number, and expansion

  2004cited by this paper
• Infinite Sequences and Series

  2003cited by this paper
• Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms

  1999cited by this paper
• Which Crossing Number Is It Anyway?

  1998cited by this paper
• Coloring Relatives of Intervals on the Plane, I: Chromatic Number Versus Girth

  1998cited by this paper
• The Probabilistic Method

  1998cited by this paper
• Colouring Relatives of Intervals on the Plane, II

  1998cited by this paper
• Separators for sphere-packings and nearest neighbor graphs

  1997cited by this paper
• Combinatorial geometry

  1995cited by this paper
• The Crossing Number

  1995influential reference
• Applications of the crossing number

  1994cited by this paper
• Intersection Graphs of Segments

  1994cited by this paper
• A turán-type theorem on chords of a convex polygon

  1992cited by this paper
• A separator theorem for nonplanar graphs

  1990cited by this paper
• NP-hardness results for intersection graphs

  1989cited by this paper
• Selected Topics in Graph Theory 2

  1985cited by this paper
• Computational Geometry

  1985cited by this paper
• A Separator Theorem for Graphs of Bounded Genus

  1984cited by this paper
• Girth in graphs

  1983influential reference
• Applications of a planar separator theorem

  1977cited by this paper
• Generalized nested dissection

  1977influential reference
• A Separator Theorem for Planar Graphs

  1977cited by this paper
• GRAPH THEORY AND PROBABILITY

  1957cited by this paper
• Induced Subdivisions in K_s,s-Free Graphs of Large Average Degree

  year unknowncited by this paper

• Edge-colouring and orientations: applications to degree-boundedness and $\chi$-boundedness

  2025cites this paper
• A structure theorem for pseudosegments and its applications

  2025cites this paper
• A Generalized Binary Tree Mechanism for Differentially Private Approximation of All-Pair Distances

  2025cites this paper
• Strongly sublinear separators and bounded asymptotic dimension for sphere intersection graphs

  2025cites this paper
• String Graphs: Product Structure and Localised Representations

  2025cites this paper
• Burling graphs in graphs with large chromatic number

  2025cites this paper
• On Geometric Bipartite Graphs with Asymptotically Smallest Zarankiewicz Numbers

  2025cites this paper
• Binary matroids and degree-boundedness for pivot-minors

  2025cites this paper
• String graphs are quasi-isometric to planar graphs

  2025cites this paper
• C4-free subgraphs of high degree with geometric applications

  2025influential citation
• A survey of Zarankiewicz problems in geometry

  2024cites this paper
• Recognition and Proper Coloring of Unit Segment Intersection Graphs

  2024cites this paper
• On the Cop Number of String Graphs

  2024cites this paper
• A survey of degree-boundedness

  2024influential citation
• Sparse Outerstring Graphs Have Logarithmic Treewidth

  2024cites this paper
• Induced-Minor-Free Graphs: Separator Theorem, Subexponential Algorithms, and Improved Hardness of Recognition

  2023cites this paper
• Powers of planar graphs, product structure, and blocking partitions

  2023cites this paper
• On the geometric thickness of 2-degenerate graphs

  2023cites this paper
• Constant-Hop Spanners for More Geometric Intersection Graphs, with Even Smaller Size

  2023cites this paper
• A structure theorem for pseudo-segments and its applications

  2023influential citation
• Efficient Approximation for Subgraph-Hitting Problems in Sparse Graphs and Geometric Intersection Graphs

  2023cites this paper
• Crossing lemma for the odd-crossing number

  2022cites this paper
• Clustered coloring of graphs with bounded layered treewidth and bounded degree

  2022cites this paper
• Nearest-Neighbor Decompositions of Drawings

  2022cites this paper
• Pair Crossing Number, Cutwidth, and Good Drawings on Arbitrary Point Sets

  2022cites this paper
• A slightly better bound on the crossing number in terms of the pair-crossing number

  2021cites this paper
• Quasiplanar graphs, string graphs, and the Erdős-Gallai problem

  2021cites this paper
• String graphs have the Erd\H{o}s-Hajnal property

  2020influential citation
• String graphs have the Erőds–Hajnal property

  2020influential citation
• Notes on Graph Product Structure Theory

  2020cites this paper
• Subexponential algorithms for variants of the homomorphism problem in string graphs

  2020cites this paper
• The structure of k-planar graphs

  2019cites this paper
• A Sharp Threshold Phenomenon in String Graphs

  2019cites this paper
• A Crossing Lemma for Families of Jordan Curves with a Bounded Intersection Number

  2019influential citation
• Planar point sets determine many pairwise crossing segments

  2019cites this paper
• Graph product structure for non-minor-closed classes

  2019cites this paper
• Clustered coloring of graphs excluding a subgraph

  2019cites this paper
• Clustered Graph Coloring and Layered Treewidth

  2019cites this paper
• Planar Graphs have Bounded Queue-Number

  2019cites this paper
• Probability and Computing

  2018cites this paper
• NSF Proposal: AF 7435149: Towards better geometric algorithms: Summarizing, partitioning and shrinking data

  2018cites this paper
• On the Size of Outer-String Representations

  2018cites this paper
• Subexponential algorithms for variants of homomorphism problem in string graphs

  2018cites this paper
• Representation Complexity of Semi-algebraic Graphs

  2017cites this paper
• Unit Incomparability Dimension and Clique Cover Width in Graphs

  2017cites this paper
• A Crossing Lemma for Jordan Curves

  2017cites this paper
• The Effect of Planarization on Width

  2017cites this paper
• Many Touchings Force Many Crossings

  2017cites this paper
• Zarankiewicz's problem for semi-algebraic hypergraphs

  2017cites this paper
• Orthogonal Tree Decompositions of Graphs

  2017influential citation
• Thickness and Antithickness of Graphs

  2017cites this paper
• Conflict-Free Coloring of String Graphs

  2017cites this paper
• $k$-Conflict-Free Coloring of String Graphs

  2017cites this paper
• Restricted String Representations

  2017cites this paper
• Separators in region intersection graphs

  2016cites this paper
• 2 Bounds on the largest acyclic set

  2015cites this paper
• Beyond the Richter-Thomassen Conjecture

  2015cites this paper
• A new separation theorem with geometric applications

  2015cites this paper
• On the Zarankiewicz problem for intersection hypergraphs

  2015influential citation
• New separation theorems and sub-exponential time algorithms for packing and piercing of fat objects

  2015influential citation
• New representation results for planar graphs

  2015cites this paper
• Selecting vertex disjoint paths in plane graphs

  2015cites this paper
• A Note on Circular Chromatic Number of Graphs with Large Girth and Similar Problems

  2014cites this paper
• Geometric Intersection Patterns and the Theory of Topological Graphs 3 Using similar ideas

  2014influential citation
• Acyclic Subgraphs of Planar Digraphs

  2014cites this paper
• Quasi-Polynomial Time Approximation Scheme for Sparse Subsets of Polygons

  2013cites this paper
• C O ] 1 3 D ec 2 01 3 Ramsey numbers of cubes versus cliques

  2013cites this paper
• String graphs and separators

  2013cites this paper
• Ramsey numbers of cubes versus cliques Citation

  2013cites this paper
• The notions of multiple packings and coverings were introduced in a geometric setting independently

  2013cites this paper
• Outerstring graphs are $\chi$-bounded

  2013cites this paper
• A Better Bound for the Pair-Crossing Number

  2013cites this paper
• On the number of edges in families of pseudo-discs

  2013cites this paper
• String graphs and separators

  2013influential citation
• Outerstring graphs are χ-bounded

  2013influential citation
• Note on the number of edges in families with linear union-complexity

  2013influential citation
• Cops and Robbers on Intersection Graphs

  2013cites this paper
• Near-Optimal Separators in String Graphs

  2013influential citation
• Decomposition of Multiple Packings with Subquadratic Union Complexity

  2013influential citation
• Applications of a New Separator Theorem for String Graphs

  2013influential citation
• Coloring Intersection Graphs of Arc-Connected Sets in the Plane

  2013influential citation
• Ramsey numbers of cubes versus cliques

  2012cites this paper
• Optimization of Railway Operations Algorithms , Complexity , and Models

  2012cites this paper
• Constructing dense graphs with sublinear Hadwiger number

  2011cites this paper
• Maximum Independent Set in 2-Direction Outersegment Graphs

  2011cites this paper
• Computing the independence number of intersection graphs

  2011cites this paper
• On grids in topological graphs

  2009cites this paper
• String graphs have the Erd˝os–Hajnal property

  year unknowncites this paper