Crossing patterns of segments

DOI10.1006/jcta.2001.3184zbMath0989.05031MaRDI QIDQ5953378

János Pach, József Solymosi

Publication date: 11 March 2002

Published in: Journal of Combinatorial Theory. Series A (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/18805c53343c3cc050d6b0c8e5c301d9cb97798e

zbMATH Keywords

crossings; straight-line segments

Mathematics Subject Classification ID

05C10: Planar graphs; geometric and topological aspects of graph theory

05C62: Graph representations (geometric and intersection representations, etc.)

Related Items

A Bipartite Strengthening of the Crossing Lemma, Turán-type results for partial orders and intersection graphs of convex sets, A bipartite analogue of Dilworth's theorem, On the obfuscation complexity of planar graphs, A bipartite strengthening of the crossing Lemma, Crossing patterns of semi-algebraic sets, Dependent random choice

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Upper bounds for configurations and polytopes in \({\mathbb{R}}^ d\)
• String graphs. II: Recognizing string graphs is NP-hard
• String graphs requiring exponential representations
• Intersection graphs of curves in the plane
• Graphs drawn with few crossings per edge
• Intersection graphs of segments
• A positive fraction Erdős-Szekeres theorem
• Not all graphs are segment \(T\)-graphs
• A left-first search algorithm for planar graphs
• Crossing-Free Subgraphs
• Multivariate regression depth
• Lower Bounds for Approximation by Nonlinear Manifolds
• On the Betti Numbers of Real Varieties
• On a problem of K. Zarankiewicz