Back to Search Start Over

Disjoint edges in complete topological graphs

Authors :
Andrew Suk
Source :
Symposium on Computational Geometry
Publication Year :
2011
Publisher :
arXiv, 2011.

Abstract

It is shown that every complete $$n$$ -vertex simple topological graph has at $$\varOmega (n^{1/3})$$ pairwise disjoint edges, and these edges can be found in polynomial time. This proves a conjecture of Pach and Toth, which appears as Problem 5 from Chapter 9.5 in Research Problems in Discrete Geometry by Brass, Moser, and Pach.

Details

Database :
OpenAIRE
Journal :
Symposium on Computational Geometry
Accession number :
edsair.doi.dedup.....b13bc8a148a35bf923c923e41318639f
Full Text :
https://doi.org/10.48550/arxiv.1110.5684