On the Crossing Number of Complete Graphs with an Uncrossed Hamiltonian Cycle

2013/09/11 by Kane, Daniel M.
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.1309.2958

Abstract

We prove new lower bounds on the crossing number of a complete graphs assuming that it is drawn in such a way that it contains a Hamiltonian cycle with no crossings.

Related

• Towards Crossing-Free Hamiltonian Cycles in Simple Drawings of Complete Graphs
• Tight Upper Bounds on the Crossing Number in a Minor-Closed Class
• On a conjecture of Pach-Spencer-Tóth for graph crossing numbers
• On the Uncrossed Number of Graphs
• Generalizations of the Crossing Lemma