Book crossing numbers of the complete graph and small local convex crossing numbers

2016/07/01 by Ábrego, Bernardo M., Dandurand, Julia, Fernández-Merchant, Silvia +2 · 1 citation
#05C10 #05C62 #52C10 #68R10 #Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.1607.00131

Abstract

A k -page book drawing of a graph G is a drawing of G on k halfplanes with common boundary l , a line, where the vertices are on l and the edges cannot cross l . The k -page book crossing number of the graph G , denoted by ν_k(G) , is the minimum number of edge-crossings over all k -page book drawings of G . Let G=K_n be the complete graph on n vertices. We improve the lower bounds on ν_k(K_n) for all k≥ 14 and determine ν_k(K_n) whenever 2 < n/k ≤ 3 . Our proofs rely on bounding the number of edges in convex graphs with small local crossing numbers. In particular, we determine the maximum number of edges that a convex graph with local crossing number at most ℓ can have for ℓ≤ 4 .

Cited by

• On the maximum number of edges of outer k-planar graphs

Related

• Tight Upper Bounds on the Crossing Number in a Minor-Closed Class
• Generalizations of the Crossing Lemma
• On the Maximum Crossing Number
• Improvement on the crossing number of crossing-critical graphs
• Using Block Designs in Crossing Number Bounds