{"id":"13f9acd5-ee63-46f9-8f36-ddce5994989e","arxiv_id":"1908.03153","paper_version":2,"verdict":"ACCEPT","confidence":"HIGH","novelty_score":7.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"There exist graphs where avoiding forbidden crossing patterns forces linearly many crossings, while unconstrained drawings need only a constant number of crossings.","lead":"This paper constructs graphs whose drawings must contain many crossings if certain local crossing patterns are forbidden, even though a drawing with only a handful of crossings exists. The results give tight or first lower bounds on the crossing ratio for 1-planar, quasi-planar, and fan-planar graphs.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"No significant objection identified: the tight 1-planar ratio is the only non-self-contained part, relying on the cited Korzhik-Mohar rigidity theorem, but the citation is credible and no internal gap was found.","rationale":"I re-read the three constructions and their proofs. The quasi-planar argument (Lemma 5 and the closed-curve argument in Theorem 4) and the fan-planar argument (Theorem 7) are clean and self-contained; their lower bounds do not depend on any external result. The 1-planar lower bound is the only place where a non-proved external theorem is load-bearing: the rigidity of H_ell is used to fix the embedding of P so that the dual must be forced into the polar faces. The reader's weakest_assumption identifies exactly this step, and I agree with that assessment. I additionally looked for internal gaps in Lemma 2; its case analysis is condensed but consistent with the structural description of P, and I found no concrete counterexample. Because the external theorem is peer-reviewed and the paper's use of it is plausible, the correct disposition is to leave the reader's ACCEPT unchanged.","tokens_in":8871,"tokens_out":31617,"duration_ms":314964,"concrete_test":"Consult the exact statement in Korzhik-Mohar [16] for the medial-extension graphs H_ell and check the threshold on ell for which the unique 1-planar embedding claim is proven; confirm that it covers every ell>=7 used in Theorem 1. If the theorem requires a larger ell or applies to a different graph family, Theorem 1 would need a revised construction.","verdict_should_be":"UNCHANGED","load_bearing_attack":"No significant objection identified. The central claim is supported by three constructions; the quasi-planar (Theorem 4) and fan-planar (Theorem 7) proofs are self-contained and sound. The 1-planar result in Theorem 1 is load-bearing on the Korzhik-Mohar theorem: H_ell must have exactly one 1-planar embedding on the sphere, and that embedding must be crossing-free. Lemma 2 then forces the dual P* into the polar faces, giving cr_1-pl(G_ell)=n-2. If H_ell admitted another 1-planar embedding, P would not be rigid and the binding/special-edge argument could fail, so the exact ratio would not follow. The paper cites [16] without restating the theorem, so this is the least locally verifiable step, but I found no reason to doubt its correctness or its applicability at ell>=7.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper investigates the gap between the ordinary crossing number and the crossing number restricted to three beyond-planar drawing styles: 1-planar, quasi-planar, and fan-planar drawings. It constructs, for each of these classes, n-vertex graphs for which every drawing respecting the local restriction has Ω(n) crossings, while an unrestricted drawing has only O(1) crossings. For 1-planar graphs the authors obtain the tight ratio n/2-1 by a graph G_l with cr_1-pl(G_l)=n-2 and cr(G_l)=2 (Theorem 1), using a rigid graph from Korzhik and Mohar together with its dual and binding edges. For quasi-planar and fan-planar graphs they prove lower bounds of Ω(n) with unrestricted crossing number at most 3 (Theorems 4 and 7), and they extend the quasi-planar construction to k-quasi-planar graphs (Corollary 6). The proofs are based on explicit constructions and a simple counting lemma (Lemma 5), with a lengthy case analysis in Appendix A supporting the 1-planar result.","tokens_in":8992,"tokens_out":17368,"duration_ms":169363,"significance":"The paper answers a natural and timely question in beyond-planar graph drawing: avoiding forbidden crossing patterns can force a linear number of crossings even when a few crossings would suffice without those restrictions. The 1-planar result is tight and therefore completely settles the ratio for that class, while the quasi-planar and fan-planar results give linear lower bounds that are within a linear factor of the trivial upper bound. The main strengths are the explicitness of the constructions, the elementary nature of Lemma 5, and the detailed case analysis in Appendix A. There are no fitted parameters or circular arguments; the only non-self-contained ingredient is the cited Korzhik-Mohar rigidity theorem, which is credible and appears to apply as stated. This is a solid contribution that will be of interest to researchers in graph drawing and crossing numbers.","major_comments":[],"minor_comments":[{"comment":"The equality cr_1-pl(G_l)=n-2 relies on the Korzhik-Mohar rigidity theorem for the graph H_l, but the precise statement of that theorem and the range of l for which it is valid are not given. Since this is the only non-self-contained step in the tightness proof, I recommend stating the theorem explicitly (or at least its exact consequence used here) so that the reader can verify the applicability to the H_l used in the construction.","section":"Section 2, Theorem 1"},{"comment":"The statement says 'For every l >= 6', but Theorem 1 and the case analysis in Lemma 2 require l >= 7 (for example, the argument uses 'at most 4 < l-2 edges' on the boundary of a face). Please correct the range or explain why the multigraph replacement changes the threshold.","section":"Corollary 3"},{"comment":"The stated vertex count n=2k(l+1)+1 does not match the construction described immediately above it, namely the same construction as Theorem 4 with the cycle length changed to 2k. That construction has 2k+1 vertices in the base graph and 4k(l-1) subdivision vertices, giving n=4kl-2k+1, not 2k(l+1)+1. Please correct the formula (the correct count is 2k(2l-1)+1) or clarify the intended construction.","section":"Corollary 6"},{"comment":"The phrase 'the unique face of size 6 in G''' may confuse readers, because G' contains a wheel on seven vertices and has several faces. It should be clarified that the face in question is the face bounded by the (subdivided) 6-cycle after x is placed inside the cycle.","section":"Section 3, proof of Theorem 4"},{"comment":"The proof of Lemma 2 is intricate and depends heavily on the drawings in Figures 4a-4d. Please ensure that these figures remain legible in the final version and that the captions indicate which part of the case analysis each figure illustrates.","section":"Appendix A, Lemma 2"}],"recommendation":"minor_revision","confidential_remarks":"The paper is technically sound and the central claims are convincing. The revisions I am requesting are local corrections to corollary statements and a few clarifying additions; I do not see a need for another full review after these are fixed."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"This paper answers a natural question in beyond-planar graph drawing: forbidding local crossing patterns can force linearly many crossings even when the unrestricted crossing number is constant, and the 1-planar bound is tight. The proofs are explicit constructions, well explained, and the main results are new.\n\nWhat's actually new: the paper defines the k-planar, quasi-planar, and fan-planar crossing numbers as the minimum crossings under the respective restrictions, and studies the ratio to the ordinary crossing number. It proves that for each of the three classes there are n-vertex graphs with restricted crossing number Ω(n) while the unrestricted crossing number is 2 or 3. The 1-planar result is tight: it matches the trivial upper bound n/2−1, and the graph has exactly n−2 crossings in any 1-planar drawing. The quasi and fan-planar results are linear lower bounds, leaving a quadratic gap to the upper bound, which the paper honestly flags as open. The constructions are explicit and use reasonably simple building blocks: a rigid planar piece for the 1-planar case, and path bundles for the others. Lemma 5 is a neat trick that does a lot of work.\n\nThe main soft spot: the tight 1-planar ratio leans on the Korzhik–Mohar theorem that the graph H_ell has a unique 1-planar embedding, and that embedding is planar. The paper cites this without restating it. That's a reasonable choice, but it means the tightness claim is only as trustworthy as that theorem, which is from a reputable source (J. Graph Theory, 2013) and I have no reason to doubt. The rest of the 1-planar proof is a detailed case analysis in Appendix A; I did not find a gap. The quasi and fan-planar proofs are self-contained and solid.\n\nMinor notes: the paper is a preprint (v2, Sep 2019), and the writing is clear. The open problems section is honest about the gap for quasi and fan. There's also a remark in Appendix B about an alternative redrawing proof, which I didn't need to use. Citation pattern looks appropriate, no self-citation padding.\n\nVerdict: this is a solid paper. It will be useful to anyone working on crossing numbers or beyond-planar graph classes. I'd send it to a serious referee; it merits publication at a graph drawing venue. I'd cite it if I work on related problems.","headline":"A clean set of constructions showing that restricted crossing numbers can exceed the unrestricted one by a linear factor, with a tight 1-planar bound.","tokens_in":9547,"tokens_out":4600,"would_cite":true,"duration_ms":45501,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C10","68R10"],"pacs":[],"model":"deepseek-v4-flash","headline":"For 1-planar, quasi-planar, and fan-planar graphs, forbidding certain local crossing patterns can force a linear number of crossings even when a constant number would suffice.","keywords":["crossing number","beyond-planar graphs","1-planar graphs","quasi-planar graphs","fan-planar graphs","crossing ratio","graph drawing"],"falsifier":"For $\\ell = 7$ in Theorem 1, the graph $G_7$ has $n = 79$ vertices; the theorem predicts $\\mathrm{cr}_{1\\text{-}\\mathrm{pl}}(G_7) = 77$ and $\\mathrm{cr}(G_7) = 2$. Drawing $G_7$ in any 1-planar way with fewer than 77 crossings, or finding an unrestricted drawing with only 1 crossing, would refute the claimed tight ratio. More directly, locating a second 1-planar embedding of the rigid graph $H_7$ on the sphere would break the rigidity premise and the entire lower-bound argument.","tokens_in":8657,"feed_emoji":"✖️","tokens_out":11075,"duration_ms":94199,"temperature":0.7,"pith_summary":"The paper asks whether forbidding local edge-crossing patterns - such as an edge being crossed twice, three mutually crossing edges, or fan patterns - can force far more crossings than are strictly necessary. It answers yes for three prominent classes of beyond-planar graphs. For 1-planar graphs the effect is maximal: for every $\\ell \\ge 7$ there is a graph $G_\\ell$ on $n = 11\\ell+2$ vertices whose every 1-planar drawing has $n-2$ crossings, while the same graph can be drawn with only 2 crossings. For quasi-planar and fan-planar graphs the paper constructs $n$-vertex examples where any drawing respecting the local rule has at least a linear number of crossings, yet 3 crossings (or fewer) suffice without the rule. The results show that the visual restriction itself, not the graph's intrinsic complexity, is what forces the large crossing count.","feed_headline":"Restricted drawings can force a linear crossing blow-up","feed_subtitle":"Even when 2 or 3 crossings would suffice, obeying the rule forces linearly many.","key_machinery":"The central objects are three rigid constructions, each built to make a prohibited crossing pattern astronomically costly. For 1-planar graphs, the construction uses a graph $P$ (a medial extension of the Cartesian product of a length-2 path and a length-$\\ell$ cycle) whose only 1-planar embedding on the sphere is planar. The graph $G_\\ell$ adds $P$'s planar dual $P^*$, binding edges that force the dual vertex $f^*$ to lie in the large polar face $f$ of $P$, and a special edge $(x,y^*)$ that is crossed at least twice in the planar embedding but can be drawn crossing-free in the unique non-planar 1-planar embedding, where every edge of $P$ crosses every edge of $P^*$ once. For quasi-planar and fan-planar bounds, the mechanism is an 'extended edge': two independent edges whose endpoints are joined by $\\ell-1$ internally disjoint length-2 paths. Lemma 5 shows that if the two base edges cross, then at least $\\ell$ crossings must occur; the constructions then force either such a crossing or, through a separating curve, a bundle of paths crossing a special edge. The fan-planar variant instead packs $\\ell$ subdivisions of $K_{3,3}$ that all share one edge, so each requires a distinct crossing, and fan-planarity rules out the only draw that could merge two crossings.","core_discovery":"Formally, the paper proves three separation theorems. Theorem 1: for every $\\ell \\ge 7$ the 1-planar graph $G_\\ell$ with $n = 11\\ell+2$ vertices satisfies $\\mathrm{cr}_{1\\text{-}\\mathrm{pl}}(G_\\ell) = n - 2$ and $\\mathrm{cr}(G_\\ell) = 2$, making the ratio exactly $n/2 - 1$, the largest possible because any 1-planar drawing of an $n$-vertex graph has at most $n-2$ crossings. Theorem 4: for every $\\ell \\ge 2$ a quasi-planar graph with $n = 12\\ell - 5$ vertices has quasi-planar crossing number at least $\\ell$ and unrestricted crossing number at most 3, giving ratio $\\Omega(n)$; the proof extends to $k$-quasi-planar graphs with ratio $\\Omega(n/k^3)$ (Corollary 6). Theorem 7: for every $\\ell \\ge 2$ a fan-planar graph with $n = 9\\ell + 1$ vertices has fan-planar crossing number exactly $\\ell$ and unrestricted crossing number 3, again giving ratio $\\Omega(n)$. Corollary 3 generalizes the 1-planar bound to $k$-planar multigraphs with ratio at least $k(n-2)/2$.","pith_inferences":["The dual-interleaving template behind Theorem 1 is likely reusable: any rigid graph with a unique embedding and a polar face structure might yield a similar separation when its dual is bound to it, so one could test it on other uniquely-embeddable graph families.","The redrawing remark in Appendix B suggests a clean structural lemma: in these extremal examples every bundle of length-two paths can be assumed to run along a single trajectory without increasing crossings. That lemma, if formalized, would simplify future lower-bound proofs for crossing numbers under local pattern restrictions.","The paper conjectures that the quasi-planar/fan-planar ratio can reach the quadratic upper bound; if true, even single forbidden local patterns would force a blow-up of the same order as the edge-count maximum, which would sharpen the folklore that restrictions beyond planarity are cheap.","One could push the separation further by asking for trade-offs: for each function $f(n)$, how large must the unrestricted crossing number be before the gap between restricted and unrestricted space becomes sublinear? The present constructions only handle constant unrestricted crossing numbers."],"forward_implications":["For 1-planar graphs the crossing ratio is exactly $n/2 - 1$: no 1-planar family can force a larger gap between the best 1-planar and best unrestricted drawing.","For $k$-planar multigraphs the ratio is at least $k(n-2)/2$, so allowing more crossings per edge widens the forced gap (Corollary 3).","For quasi-planar graphs the ratio is $\\Omega(n)$ even when the unrestricted crossing number is at most 3, and for $k$-quasi-planar graphs it is $\\Omega(n/k^3)$ (Theorem 4, Corollary 6).","For fan-planar graphs the ratio is $\\Omega(n)$ with unrestricted crossing number exactly 3 (Theorem 7).","The constructions provide explicit examples where the local-restriction crossing number exceeds the unrestricted crossing number by an arbitrarily large linear factor, not merely by a constant."],"supporting_citations":[{"why":"Supplies the rigid graph $H_\\ell$ whose unique 1-planar embedding is planar, the backbone of the 1-planar construction.","marker":"[16]"},{"why":"Provides the upper bound $\\mathrm{cr}_{1\\text{-}\\mathrm{pl}}(G) \\le n-2$ and the 1-planarity definition that makes the $n/2 - 1$ ratio tight.","marker":"[15]"},{"why":"Defines the beyond-planar graph classes and gives the edge-density bounds $O(n)$ and $O(n^2)$ used to frame the ratios.","marker":"[8]"},{"why":"Gives the $k$-quasi-planar edge bound $c_k n \\log n$ used to derive the upper bound $f(k)n^2 \\log^2 n$ in Corollary 6.","marker":"[23]"},{"why":"Supplies the fan-planarity forbidden-pattern definition used in the fan-planar lower bound.","marker":"[13]"}],"fun_headline_variants":["Restrictions force crossing numbers up to linear blow-up","1-planar, quasi, fan: rules multiply crossings","Beyond-planar drawings: obeying rules costs many crossings","Even a few crossings become linearly many under rules","Rule-bound drawings can blow up crossing counts"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The 1-planar ratio bound rests on the rigidity premise that the graph $H_\\ell$ (and hence the built $P$) has exactly one 1-planar embedding on the sphere; if another embedding existed, the binding and special edges might be drawable without forcing the dual into the polar faces, and the $n-2$ lower bound could collapse.","fun_headline_variants_meta":{"raw":{"variants":["Restrictions force crossing numbers up to linear blow-up","1-planar, quasi, fan: rules multiply crossings","Beyond-planar drawings: obeying rules costs many crossings","Even a few crossings become linearly many under rules","Rule-bound drawings can blow up crossing counts"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000653,"raw_usage":{"total_tokens":2971,"prompt_tokens":901,"completion_tokens":2070,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":517,"completion_tokens_details":{"reasoning_tokens":1995}},"tokens_in":517,"tokens_out":2070,"duration_ms":15365,"temperature":1.0,"reasoning_tokens":1995,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T14:21:50.240843+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"For $\\ell = 7$ in Theorem 1, the graph $G_7$ has $n = 79$ vertices; the theorem predicts $\\mathrm{cr}_{1\\text{-}\\mathrm{pl}}(G_7) = 77$ and $\\mathrm{cr}(G_7) = 2$. Drawing $G_7$ in any 1-planar way with fewer than 77 crossings, or finding an unrestricted drawing with only 1 crossing, would refute the claimed tight ratio. More directly, locating a second 1-planar embedding of the rigid graph $H_7$ on the sphere would break the rigidity premise and the entire lower-bound argument.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the upper bound $\\mathrm{cr}_{1\\text{-}\\mathrm{pl}}(G) \\le n-2$ and the 1-planarity definition that makes the $n/2 - 1$ ratio tight."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Gives the $k$-quasi-planar edge bound $c_k n \\log n$ used to derive the upper bound $f(k)n^2 \\log^2 n$ in Corollary 6."}],"review_version":1}