{"id":"7ec0cd41-50e0-432a-ad7a-5fa0b70370bd","arxiv_id":"1909.00223","paper_version":1,"verdict":"ACCEPT","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"For every k at least 2, every simple k-planar graph can be redrawn as a simple (k+1)-quasiplanar graph.","lead":"The paper proves that every graph drawing with at most k crossings per edge can be redrawn so that no k+1 edges all cross one another, for every k at least 2. This tightens the known relationship between two prominent families of beyond-planar graphs.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"No significant objection identified.","rationale":"The reader identified the Lemma 19 reassignment step as the weakest assumption, and I agree that it is where scrutiny should focus: it is the most compressed argument in the proof and the k=2 case depends on it. However, the concern does not amount to a real flaw. Lemma 4 gives a strong surplus of 5 for every subset of crossings, and for crossings whose regions lie inside R(c) all their endpoints lie inside R(c) as well, so discarding the boundary cycle vertices leaves enough candidates for Hall's theorem, even after reserving v for X1. The proof would benefit from displaying this calculation, but it is correct as written. I also checked the k>=3 argument and the simplicity repair in Lemma 27; they are dense but internally consistent. Since the central claim is supported and no load-bearing error surfaced, the appropriate verdict is unchanged.","tokens_in":29301,"tokens_out":38923,"duration_ms":366580,"concrete_test":"Independently re-derive the Hall bound for the restricted sub-instance in Lemma 19: for every subset A' of crossings with R(X) subset of R(c), verify that all endpoints of crossings in A' lie in R(c), then apply Lemma 4 to obtain |N(A')| >= |A'| + 5, subtract the at most three cycle vertices and the pre-assigned vertex v, and confirm at least |A'| available targets remain. If this calculation holds for all A', the reassignment step is valid and the k=2 termination argument is sound.","verdict_should_be":"UNCHANGED","load_bearing_attack":"No significant objection identified. The densest point is the reassignment step in Lemma 19, where the paper compresses the Hall check for crossings with R(X) contained in R(c) into one sentence. If that Hall condition failed, the termination measure Vns would not strictly decrease and the k=2 case would collapse. Reading the step carefully, however, the appeal to Lemma 4 is sufficient: for any subset A' of those crossings, all endpoints N(A') lie in R(c), and Lemma 4 gives |N(A')| >= |A'| + 5; after discarding the at most three vertices of the cycle c (and the newly assigned vertex v, which cannot be occupied by an exterior crossing without violating planarity of the conflict digraph), at least |A'| + 1 interior vertices remain, so Hall's condition holds. Lemma 27 is intricate, but its case distinction is directed at precisely the pairs characterized in Lemma 26 and I found no load-bearing gap there. The main theorem therefore appears sound.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proves Theorem 1: for every k ≥ 2, every simple topological graph in which each edge is crossed at most k times admits an isomorphic simple topological drawing with no k+1 pairwise crossing edges. The proof is constructive. It first eliminates tangled (k+1)-crossings, then selects an injective function f assigning to each (k+1)-crossing a rerouting vertex, and a function g selecting the edge to be rerouted. A global rerouting is then applied, followed by home reroutings. For k = 2, a conflict digraph is used to rule out the only two possible remaining 3-crossing configurations (twins and whirls). For k ≥ 3, quasiplanarity follows from a separate counting argument, and a final redrawing step removes violations of simplicity. The main inclusion is stated as Theorem 1 and the proof is self-contained apart from classical facts such as Hall's theorem, Euler's formula, the Jordan curve theorem, and the nonplanarity of K3,3.","tokens_in":29392,"tokens_out":25966,"duration_ms":225934,"significance":"If correct, this is a notable structural result: it establishes the first nontrivial inclusion between the k-planar and the k-quasiplanar hierarchies for simple topological graphs, and it does so with an explicit redrawing that preserves the abstract graph. The proof introduces reusable techniques, notably the untangling procedure for (k+1)-crossings and the global rerouting framework based on matching arguments and a conflict digraph. The argument has no free parameters and builds on standard tools. The authors are also explicit about limitations: the result does not extend to k = 1, and the question for non-simple k-planar graphs remains open. I checked the densest step highlighted in the review, the Hall reassignment in Lemma 19, and the concern does not land as a correctness issue: the slack in Lemma 4 is sufficient for the required matching once the bound is stated with the necessary exclusions.","major_comments":[],"minor_comments":[{"comment":"The Hall step is compressed: after setting f′(X1) = v, the proof should explicitly exclude not only the at most three vertices of the cycle c but also the newly occupied vertex v from the candidate set for the remaining 3-crossings. Lemma 4 gives |N(A′)| ≥ |A′| + 5 for every subset A′ of those crossings, so after excluding these at most four forbidden vertices Hall's condition still holds with at least one unit of slack. Please spell out this argument in the text.","section":"§6.2, Lemma 19"},{"comment":"The sentence 'a short cycle has a directed edge between any two of its vertices' is not literally true for directed 3-cycles. In the two places where this assertion is used, the required reverse edge follows from the fact that the edge of the other cycle lies outside the cycle, so the statement should be replaced by the precise local argument to avoid confusion.","section":"§6.1, Lemmas 15 and 18"},{"comment":"The first sentence of Property 1 contains a duplicated phrase: 'k-planar simple topological graph topological graph'.","section":"§2, Property 1"},{"comment":"The expression 'f′(X) ∈ V ∈ int c' is a typo and should read 'f′(X) ∈ V ∩ int(c)'.","section":"§6.2, definition of F(f,c,X1,v)"},{"comment":"The derivation of claim (B) from claim (A) is abbreviated; a short explanation of why a new non-smooth cycle containing v1 would have to be bad would improve readability.","section":"§6.2, Lemma 19"}],"recommendation":"minor_revision","confidential_remarks":"The paper is a strong contribution and the central theorem appears sound. The only issues I found are local presentation gaps, chiefly the compressed Hall argument in Lemma 19 and a few wording imprecisions about 3-cycles in the conflict digraph. These can be addressed without changing the proof strategy. The self-citations to WG 2017 and MFCS 2017 are appropriate for preliminary versions, and the manuscript fits the journal's scope."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The main result—every simple k-planar topological graph is simple (k+1)-quasiplanar for k≥2—checks out on a careful read. The proof is long but coherent: untangle all (k+1)-crossings, assign each to a vertex via Hall, reroute one edge per crossing, and then fix the k=2 case with the twin/whirl analysis and the conflict digraph. The rerouting framework is genuinely useful and the k≥3 part is a real technical achievement. I found no load-bearing gap. The densest moment is Lemma 19, where the Hall condition for the reassignment inside R(c) is compressed into a sentence; the stress-test note is right that Lemma 4 supplies enough slack after excluding the cycle vertices. Lemma 27 is intricate, but the case distinction matches the characterization in Lemma 26, and the simplicity argument holds together as far as I can tell. A formal proof assistant would be nice, but its absence is not a flaw.\n\nTwo things keep this from being a completely fresh result. The paper's own footnote says preliminary versions appeared at WG 2017 and MFCS 2017, and the k=2 case is Hoffmann–Toth in MFCS 2017. So the statement of Theorem 1 is not new. What is new is the complete proof for all k and the unified untangling/rerouting machinery. That is enough to justify publication in a good venue, but not enough to sell the paper as a new theorem. The self-citations are legitimate: they point to the earlier announcements, and the proof here is self-contained rather than circular.\n\nThe weaknesses are real but minor: the proof is long enough that a referee needs patience, the k=2 section is the most delicate, and the simplicity cleanup for k≥3 is hard to verify by hand. None of these sinks the paper. I would send this to a serious referee, and I would expect acceptance after a careful check of Lemmas 19 and 27. If I were working on beyond-planar graph classes, I would cite this as the definitive full proof of the inclusion.","headline":"The theorem is real and the proof mostly holds, but the headline inclusion was already announced in the cited WG 2017 and MFCS 2017 papers, so the contribution here is the full proof and the unified technique, not the statement itself.","tokens_in":30062,"tokens_out":1550,"would_cite":true,"duration_ms":17634,"reading_group":"yes","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":"Every simple k-planar graph is a simple (k+1)-quasiplanar graph for all k≥2.","keywords":["k-planar graphs","k-quasiplanar graphs","simple topological graphs","graph drawing","edge crossings","beyond planar graphs","conflict digraph","matching"],"falsifier":"Search all small 2-planar simple topological graphs and all injective choices of f; if some maximal nonsmooth cycle c has fewer distinct vertices inside R(c) (minus the at most three cycle vertices) than the number of 3-crossings whose regions lie inside R(c), then the matching condition fails and the reassignment step of the k=2 proof cannot be executed. Finding such a configuration would locate exactly where the argument collapses; an exhaustive search that finds none would support the paper's one-sentence claim.","tokens_in":29047,"feed_emoji":"✏️","tokens_out":8837,"duration_ms":75105,"temperature":0.7,"pith_summary":"This paper proves a containment between two hierarchies of graphs defined by crossing restrictions. A graph is k-planar if it can be drawn with every edge crossed at most k times; it is (k+1)-quasiplanar if it can be drawn with no k+1 edges pairwise crossing. The theorem states that for every k≥2, every simple k-planar topological graph can be redrawn, with the same abstract graph, as a simple (k+1)-quasiplanar topological graph. The previous immediate bound was that k-planar drawings are (k+2)-quasiplanar, so the proof tightens the inclusion by one and gives the first nontrivial bridge between the two hierarchies. The construction is explicit: it reroutes edges of the given drawing until all forbidden configurations disappear.","feed_headline":"k-planar graphs redraw into (k+1)-quasiplanar graphs","feed_subtitle":"A constructive rerouting shows any drawing with at most k crossings per edge can avoid k+1 pairwise crossing edges.","key_machinery":"The engine of the proof is an edge-rerouting operation on an 'untangled' (k+1)-crossing, a set of k+1 pairwise crossing edges whose 2k+2 endpoints all lie on a single face of the arrangement those edges form. For each such crossing X the paper selects a vertex f(X) on the crossing and an edge g(X) in the crossing, then redraws g(X) through a disk around the crossing and along a crossing-free boundary edge, dissolving the crossing. The choices of f and g must be injective and compatible. For k=2 this is handled by a plane conflict digraph whose 2-cycles and 3-cycles encode the twin and whirl configurations that can survive a naive rerouting; the paper shows how to modify f so that all short nonghost cycles are smooth, then uses a bipartite matching condition to choose g so that every remaining cycle is broken. For k≥3, injectivity alone prevents new (k+1)-crossings, and a final redrawing step repairs multiple or adjacent crossings.","core_discovery":"The central claim is Theorem 1: for every integer k≥2, every simple k-planar topological graph is isomorphic to a simple (k+1)-quasiplanar topological graph. Concretely, from any drawing in which each edge is crossed at most k times, the paper builds another drawing of the same abstract graph in which no k+1 edges are pairwise crossing. The new drawing may allow an edge to be crossed more than k times, but it remains a simple topological graph: adjacent edges do not cross and no two edges cross more than once. The authors note the result cannot extend to k=1, because 2-quasiplanar graphs are exactly planar graphs, while 1-planar graphs need not be planar.","pith_inferences":["The construction selects edges via injective matchings, so it is plausibly implementable as an algorithm that rewrites a k-planar drawing into a (k+1)-quasiplanar one; the paper does not state a running time, and measuring the number of rerouted edges on small examples would be a natural next step.","The k=2 bottleneck is the existence of enough distinct interior vertices after deleting up to three cycle vertices; this suggests that any counterexample to the theorem would first surface as a violation of the bipartite matching condition in a small conflict graph.","The conflict-digraph technique for breaking twin and whirl configurations is not tied to the specific parameters k=2 and 3, and may transfer to other beyond-planar containment questions where forbidden configurations form short cycles."],"forward_implications":["For every k≥2, the class of simple k-planar graphs is contained in the class of simple (k+1)-quasiplanar graphs, so the two hierarchies are separated by exactly one step.","For k=2 and k=3, the containment extends to all k-planar graphs, not only simple ones, because every k-planar graph in that range admits a simple k-planar drawing.","Known upper bounds on the edge count of (k+1)-quasiplanar simple graphs automatically become upper bounds on the edge count of k-planar simple graphs, since every such graph has a (k+1)-quasiplanar drawing.","The result is tight in the sense that k=1 is impossible: 2-quasiplanar graphs are planar, and 1-planar graphs are not all planar."],"supporting_citations":[],"fun_headline_variants":["Redraw k-planar edges to avoid k+1 pairwise crossings","k-planar graphs become (k+1)-quasiplanar after rerouting","From k-planar to (k+1)-quasiplanar: a redrawing","Every k-planar graph has a (k+1)-quasiplanar drawing","Transform k-planar drawings into (k+1)-quasiplanar ones"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The proof assumes that after reassigning one 3-crossing to a vertex inside a chosen maximal nonsmooth cycle, the remaining 3-crossings inside that cycle can still be matched to distinct interior vertices even after excluding up to three vertices of the cycle, an assertion it states without displaying the full matching-condition check.","fun_headline_variants_meta":{"raw":{"variants":["Redraw k-planar edges to avoid k+1 pairwise crossings","k-planar graphs become (k+1)-quasiplanar after rerouting","From k-planar to (k+1)-quasiplanar: a redrawing","Every k-planar graph has a (k+1)-quasiplanar drawing","Transform k-planar drawings into (k+1)-quasiplanar ones"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000498,"raw_usage":{"total_tokens":2360,"prompt_tokens":783,"completion_tokens":1577,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":399,"completion_tokens_details":{"reasoning_tokens":1470}},"tokens_in":399,"tokens_out":1577,"duration_ms":11536,"temperature":1.0,"reasoning_tokens":1470,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T05:58:44.544193+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Search all small 2-planar simple topological graphs and all injective choices of f; if some maximal nonsmooth cycle c has fewer distinct vertices inside R(c) (minus the at most three cycle vertices) than the number of 3-crossings whose regions lie inside R(c), then the matching condition fails and the reassignment step of the k=2 proof cannot be executed. Finding such a configuration would locate exactly where the argument collapses; an exhaustive search that finds none would support the paper's one-sentence claim.","supporting_citations":[],"review_version":1}