Disjoint edges in complete topological graphs

2011/10/26 by Andrew Suk, Suk, Andrew · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #Computational Geometry (cs.CG) #Digital Image Processing Techniques #FOS: Computer and information sciences #FOS: Mathematics #Limits and Structures in Graph Theory #cs.CG #math.CO

paper · pdf · doi:10.48550/arxiv.1110.5684

openalex publication_date 2011/10/26 · arxiv created 2012/08/14 · arxiv updated 2012/08/16 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

It is shown that every complete n-vertex simple topological graph has at least Omega(n^1/3) pairwise disjoint edges, and these edges can be found in polynomial time. This proves a conjecture of Pach and Tóth.

Cited by

• Unavoidable patterns and plane paths in dense topological graphs

Related

• Many disjoint edges in topological graphs
• Disjoint edges in topological graphs and the tangled-thrackle conjecture
• Estimating the number of disjoint edges in simple topological graphs via cylindrical drawings
• Note on disjoint faces in simple topological graphs
• Unavoidable patterns in complete simple topological graphs