Back to Search
Start Over
Disjoint edges in complete topological graphs
- 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.
- Subjects :
- Vertex (graph theory)
Computational Geometry (cs.CG)
FOS: Computer and information sciences
Discrete geometry
Disjoint sets
Computer Science::Computational Geometry
Topology
Theoretical Computer Science
Combinatorics
FOS: Mathematics
Discrete Mathematics and Combinatorics
Mathematics::Metric Geometry
Mathematics - Combinatorics
Cograph
Time complexity
Mathematics
Discrete mathematics
Conjecture
Topological graph
1-planar graph
Disjoint union (topology)
Computational Theory and Mathematics
Topological graph theory
Computer Science - Computational Geometry
Multiple edges
Geometry and Topology
Combinatorics (math.CO)
Subjects
Details
- Database :
- OpenAIRE
- Journal :
- Symposium on Computational Geometry
- Accession number :
- edsair.doi.dedup.....b13bc8a148a35bf923c923e41318639f
- Full Text :
- https://doi.org/10.48550/arxiv.1110.5684