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

DOI10.1137/130925554MaRDI QIDQ4979827zbMATH OpenOpenAlexFDO

Authors Radoslav Fulek

Publication date 19 June 2014

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1307.4191

zbMATH Keywords

complete topological graphextremal combinatoricsmatching

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Theory of matrix inversion and generalized inverses (15A09) Determinants, permanents, traces, other special matrix functions (15A15) Factorization of matrices (15A23)

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)$ denote the maximum number $c$ such that every simple angularly monotone drawing of a complete graph on $n$ vertices contains at least $c$ pairwise disjoint edges. We show that for every simple complete topological graph $G$ there exists $Delta$, $0<Delta<n$, such that $G$ contains at least $maxfracnDelta,c(Delta)$ pairwise disjoint edges. By combining our result with a result of T'oth we obtain an alternative proof for the best known lower bound of $Omega(n^{f}rac13)$ 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.

Recommendations

• Many disjoint edges in topological graphs
• Many disjoint edges in topological graphs
• Disjoint edges in topological graphs
• Combinatorial Geometry and Graph Theory
• Disjoint edges in complete topological graphs

Cited in

(9)

• Empty triangles in complete topological graphs
• Many disjoint edges in topological graphs
• Many disjoint edges in topological graphs
• Shooting stars in simple drawings of \(K_{m,n}\)
• Twisted ways to find plane structures in simple drawings of complete graphs
• Towards crossing-free Hamiltonian cycles in simple drawings of complete graphs
• Plane Hamiltonian cycles in convex drawings
• Plane Hamiltonian cycles in convex drawings
• Separable drawings: extendability and crossing-free Hamiltonian cycles

This page was built for publication: Estimating the number of disjoint edges in simple topological graphs via cylindrical drawings

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4979827)