Estimating the number of disjoint edges in simple topological graphs via cylindrical drawings

preprint2013arXivOpen access

Abstract

A topological graph drawn on a cylinder whose base is horizontal is \emph{angularly monotone} if every vertical line intersects every edge at most once. Let c(n)c(n) denote the maximum number cc such that every simple angularly monotone drawing of a complete graph on nn vertices contains at least cc pairwise disjoint edges. We show that for every simple complete topological graph GG there exists ΔΔ, 0<Δ<n0<Δ<n, such that GG contains at least max⁡{nΔ,c(Δ)}\max \{\frac nΔ, c(Δ)\} pairwise disjoint edges. By combining our result with a result of Tóth we obtain an alternative proof for the best known lower bound of Ω(n13)Ω(n^\frac 13) on the maximum number of pairwise disjoint edges in a simple complete topological graph proved by Suk. Our proof is based on a result of Ruiz-Vargas.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.