Crossing bound for 2-page extension of 1-page drawing
Problem 4 · arXiv:1608.07680
Status open medium confidence
Problem 4 from arXiv:1608.07680 asks for a general upper bound on the crossings of an optimal 2-page drawing of G (with fixed spine order) given a 1-page drawing with k crossings; the paper itself provides only a partial answer via the Edwards max-cut bound. A 2021 follow-up note by Ding and Huang (Graphs and Combinatorics) builds on the original work by improving values of the function f(k) for small k, but I could not access its full text to confirm whether it resolves Problem 4. No paper specifically solving the general 1-page-to-2-page bound question was found in the verified literature.
Reviewer notes. A follow-up paper titled 'A Note on the Crossing Number of the Cone of a Graph' by Ding and Huang was published in Graphs and Combinatorics in 2021 (DOI: 10.1007/s00373-021-02361-2). Search snippets indicate it shows ϕs(6)=5 and ϕs(7)=6 (exact values of f(k) for simple graphs), which concerns the f(k) function rather than the 1-page-to-2-page bound of Problem 4 specifically. The Springer URL was inaccessible (authentication redirect) and no arXiv preprint was found, so this paper is not included in since_posted per the verification requirement. The original paper's partial answer via the Edwards max-cut bound remains the only known published result directly addressing Problem 4.
Context
This problem asks: if all vertices of $G$ are incident to the outer face (equivalently, $G$ admits a 1-page drawing), what is the most efficient way to redraw some edges in a new page to reduce crossings? It is intimately related to bounding the crossing number of the cone, and the Edwards max-cut bound (Lemma 5) is applied to answer it partially.
Source paper
The crossing number of the cone of a graph
Carlos A. Alfaro, Alan Arroyo, Marek Derunár, Bojan Mohar · 2016-08-27
https://arxiv.org/abs/1608.07680
PDF source