The maximum number of edges in an outer k-planar graph on n vertices is at most (sqrt(2)+epsilon) sqrt(k) n plus a lower-order term, with epsilon tending to 0 as k grows.
Book crossing numbers of the complete graph and small local convex crossing numbers
1 Pith paper cite this work. Polarity classification is still indexing.
1
Pith paper citing it
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 $ \nu_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 $ \nu_k(K_n) $ for all $ k\geq 14 $ and determine $ \nu_k(K_n) $ whenever $ 2 < n/k \leq 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 $ \ell $ can have for $ \ell\leq 4 $.
fields
math.CO 1years
2025 1verdicts
CONDITIONAL 1representative citing papers
citing papers explorer
-
On the maximum number of edges of outer k-planar graphs
The maximum number of edges in an outer k-planar graph on n vertices is at most (sqrt(2)+epsilon) sqrt(k) n plus a lower-order term, with epsilon tending to 0 as k grows.