{"id":"258d780b-55fb-41a8-a407-8cce9b75b59f","arxiv_id":"1908.03042","paper_version":2,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"A new vertex-insertion enumeration with isomorphism pruning yields tight characterizations for the largest complete and complete bipartite graphs in k-planar, fan-planar, fan-crossing free, gap-planar, and quasiplanar classes.","lead":"This paper presents a computational technique that enumerates all topologically distinct drawings of complete and complete bipartite graphs under beyond-planarity crossing restrictions. Applied to several graph classes, it settles open questions about the largest dense graphs each class admits.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"New negative results rest on unverified exhaustive Java search; independent certificates or proofs are needed before the characterizations can be taken as theorems.","rationale":"The reader's CONDITIONAL verdict is appropriate. I found no internal contradiction in the algorithm's design: the half-pathway enumeration is plausibly complete for simple drawings, and the public implementation is genuine evidence. However, the paper's most important new contributions are negative upper bounds, and those are computational non-existence claims. Non-existence cannot be certified by an example; it requires a human proof, a machine-checked proof, or an independently verified exhaustive search. Only the fan-crossing-free characterization has a human-checkable proof in Appendix E. The simple-drawing caveat, acknowledged in Section 2, compounds this because the characterizations are not explicitly qualified as applying only to simple drawings. An independent SAT-based check of K8 would either falsify the flagship claim or materially raise confidence in the computational pipeline. Since the reader already made the verdict conditional on exactly this kind of independent support, no verdict change is needed.","tokens_in":32253,"tokens_out":16782,"duration_ms":192768,"concrete_test":"Re-encode the flagship boundary case K8 not 2-planar as a SAT instance: variables encode a rotation system and the cyclic order of crossings along each edge of a simple topological drawing of K8, with constraints that every edge is crossed at most twice; solve to completion with an independent SAT solver requiring an UNSAT certificate. If a model is found, Characterization 2 collapses; if UNSAT, apply the same independent encoding to K4,7 for 2-planarity to cover the bipartite case. This check directly tests whether the Java search's negative output is reproducible outside the original implementation.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Section 3's Theorem 1 asserts completeness of the half-pathway enumeration over simple drawings. If the theorem and the implementation are correct, the negative entries in Table 1 (e.g., K8 not 2-planar, K4,7 and K5,5 not 2-planar, K5,5 not fan-planar, K4,9 not gap-planar, K4,10/K5,7/K6,6 not 3-planar) follow. But the paper provides no proof or machine-checkable certificate for these non-membership claims; they are solely outputs of the Java program described in Appendix D. The code is public and reproducible, which is real evidence, but it is not formally verified, no version/commit is pinned, and the isomorphism test uses Properties P.1/P.2 that the authors state are sufficient but not proved necessary (Section 3); any bug in these or in the crossing-restriction logic could turn a drawing into a false negative. Appendix E supplies a human-checkable proof only for the fan-crossing-free class. Additionally, the search is over simple drawings only, and Section 2 explicitly concedes this restriction is not without loss of generality; hence the characterizations are at best for simple drawings unless that gap is closed. The upper-bound side of the paper's central claim therefore rests on computational experiment rather than proof.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes a generation technique for enumerating simple topological drawings of complete and complete bipartite graphs that satisfy beyond-planarity restrictions. The algorithm builds drawings vertex by vertex, using half-pathways in the planarization to insert edges and an isomorphism filter based on two sufficient conditions (P.1 and P.2). The authors apply the implementation to several classes and report new tight characterizations, including the claims that K8 is not 2-planar, K4,7 and K5,5 are not 2-planar, K4,10, K5,7 and K6,6 are not 3-planar, K5,5 is not fan-planar, and K4,9 is not gap-planar. For the fan-crossing free class, Appendix E contains a detailed human-checkable combinatorial proof of the characterization of complete bipartite graphs. The paper also reports drawing counts and execution times in Appendix D and makes the Java implementation publicly available.","tokens_in":32461,"tokens_out":5817,"duration_ms":66552,"significance":"If the reported characterizations are correct, the paper settles several open bounds for beyond-planarity classes and provides a new computational tool for generating topological representations. The positive certificates (e.g., 3-planar drawings of K4,9 and K5,6, the 4-planar drawings, and the quasiplanar examples) are concrete and useful. The combinatorial proof in Appendix E for the fan-crossing free case is careful and checkable, and the fact that the implementation reproduces known entries such as K6 being 1-planar and K8 being gap-planar is reassuring. However, most of the advertised new results are negative statements that currently rest on the correctness and exhaustiveness of an unverified implementation, and the paper explicitly restricts to simple drawings without proving this is without loss of generality.","major_comments":[{"comment":"The central new results are negative memberhips: e.g., \"K8 is not 2-planar\" (Characterization 2), \"K4,7 and K5,5 are not 2-planar\" (Characterization 3), \"K4,10, K5,7 and K6,6 are not 3-planar\" (Characterization 4), \"K5,5 is not fan-planar\" (Characterization 7), and \"K4,9 is not gap-planar\" (Observation 11). In every case the evidence is that the Java implementation in Appendix D failed to find a drawing. Since the implementation is not formally verified and no machine-checkable unsatisfiability certificate is provided, these are computational experiments rather than mathematical theorems. The paper should either supply independent proofs/certificates for each negative entry or explicitly restate these items as computational evidence, separate from the proven characterizations.","section":"Section 4, Table 1, Characterizations 2-7 and Observation 11"},{"comment":"The paper restricts all drawings to simple drawings and states \"this assumption is not without loss of generality [3].\" This is load-bearing because the stated if-and-only-if characterizations, such as \"Ka,b is 3-planar if and only if ...\" are claims about the standard beyond-planarity classes. If those classes admit non-simple drawings, the generated set may miss valid drawings and the negative results may be false. The authors must either prove that for complete and complete bipartite graphs the beyond-planarity classes considered here can be witnessed by simple drawings, or qualify every characterization and theorem as applying only to simple drawings.","section":"Section 2, Preliminaries"},{"comment":"Theorem 1 is the formal justification that the algorithm is exhaustive, but no proof is given; the text only says \"We summarize the above discussion in the following theorem.\" A rigorous proof is needed that every valid simple drawing can be obtained by the vertex-by-vertex construction, that the half-pathway rules and prohibited-edge conditions exactly characterize validity for each class C, and that the isomorphism filtering does not discard a representative needed to reach a drawing of G. Without this proof, the \"only if\" direction of Theorem 1 is an assertion rather than a mathematical statement.","section":"Section 3, Theorem 1"},{"comment":"The isomorphism test uses Properties P.1 and P.2, which the authors state are sufficient but not known to be necessary. Consequently, the algorithm may retain isomorphic copies, so the claim that it generates \"all non-isomorphic simple drawings\" and the \"Non-Iso\" counts in Tables 2 and 3 are not established. This does not directly invalidate the existence/non-existence characterizations, because retaining extra isomorphic drawings cannot create false negative results, but it is a gap for the enumeration contribution and for any reader who uses the reported counts.","section":"Section 3, Isomorphism testing"}],"minor_comments":[{"comment":"In the paragraph describing the recursive face mapping, \"faces incident to e1 end e2\" appears to be a typo for \"e'1 and e'2\".","section":"Section 3, Isomorphism testing"},{"comment":"The sentence \"we can directly conclude that the drawing Gamma5 cannot be a subdrawing ...\" should refer to Gamma6, not Gamma5.","section":"Appendix G, case for Gamma_6"},{"comment":"The phrase \"the edge (u2,w6) must be crossing-freee\" contains a typo: \"freee\" should be \"free\".","section":"Appendix G, Figure 30 discussion"},{"comment":"For reproducibility, the paper should pin the exact commit hash of the GitHub repository and state the Java version and any non-standard dependencies; the current reference is only to a repository URL.","section":"Appendix D"},{"comment":"The \"DFS-like variant\" of the algorithm is not described in Section 3; a precise description is needed for reproducibility, even though these observations are only positive certificates.","section":"Section 4, Observations 5 and 13"},{"comment":"Some cell formatting is confusing, e.g., the 2-planar complete bipartite row lists \"K4,5 K5,5 Char.3 [34]\" in a way that mixes membership, non-membership, and references; this should be split into clearly labeled entries.","section":"Table 1"}],"recommendation":"major_revision","confidential_remarks":"The paper's most striking results are negative characterizations supported only by an unverified exhaustive search. The authors have demonstrated in Appendix E that they can produce human-checkable proofs for at least one class, which suggests the gap is fixable, but in its current form the manuscript should not be published as a set of theorems. I would advise the editor to require either machine-checkable certificates or explicit computational-status labels for all negative claims before acceptance."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The paper is worth your time. The core idea—generate all non-isomorphic simple drawings of complete or complete bipartite graphs by incremental vertex insertion, using half-pathways to encode possible edge routings and isomorphism pruning to kill duplicates—is new and effective. It settles real open problems: K8 is not 2-planar, K5,5 is not fan-planar, K4,9 is not gap-planar, and it gives tight 2- and 3-planar bipartite characterizations. The Appendix E proof that the complete bipartite fan-crossing free graphs are exactly those with a≤2 or (a≤4 and b≤6) is a genuine human-checkable combinatorial argument, and it matches the implementation. The code is public, which is more than most theory papers offer. Credit where due: this is a solid proof-of-concept, and the fan-crossing-free case is a real theorem with a real proof.\n\nThe soft spots are the negative results. Most non-membership claims—K8 not 2-planar, K4,7, K5,5, and the larger 3-planar cases—rest entirely on the Java implementation exhausting the search space. That is reproducible evidence, but not a proof. No version or commit is pinned, the isomorphism test uses Properties P.1/P.2 which are only proved sufficient, and the code is not formally verified. A bug in the crossing-restriction logic or in the termination condition could turn a false negative into a published characterization. On the P.1/P.2 point, I disagree slightly with the stress-test note: since the properties are sufficient, discarding only happens when drawings really are isomorphic, so a failure of necessity would at worst keep extra drawings, not create false negatives. The load-bearing uncertainty is simply whether the exhaustive search really is exhaustive.\n\nThe second caveat is the simple-drawing assumption. Section 2 says explicitly it is not without loss of generality. Several of the characterizations are stated in the abstract and in Section 4 as if they describe the beyond-planarity classes in full; really they describe simple drawings only. That is a meaningful gap if the field's standard definitions allow non-simple drawings. The authors flag it, but they do not close it, and the characterizations should be worded as conditional on simplicity until they do.\n\nMinor issue: some claims in Table 1 are marked with gray and depend on other entries; that is fine, but it makes the table a bit harder to read than it should be.\n\nVerdict: the paper deserves a serious referee. It is important enough within graph drawing, the technique is reusable, and the Appendix E proof shows the authors can do the rigorous work when they choose to. I would send it to review and ask for two things: pin the code or provide machine-checkable certificates for the negative cases, and either prove the simple-drawing reduction or explicitly state all characterizations as applying to simple drawings. If the authors do that, this becomes a strong paper.","headline":"A genuinely useful enumeration technique with several new tight bounds, but the negative results are computational claims that need certificates or a pinned implementation before they can be taken as theorems.","tokens_in":33018,"tokens_out":1827,"would_cite":true,"duration_ms":23303,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C10","05C62","68R10"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper establishes exact if-and-only-if characterizations for complete and complete bipartite graphs in beyond-planarity classes by exhaustively generating all non-isomorphic topological drawings.","keywords":["beyond-planarity","topological graph drawing","k-planar graphs","fan-planar graphs","gap-planar graphs","quasiplanar graphs","complete bipartite graphs","drawing enumeration"],"falsifier":"Find, by independent exhaustive enumeration or by construction, a simple 2-planar drawing of $K_{4,7}$ or $K_{5,5}$, a fan-planar drawing of $K_{5,5}$, or a 2-planar drawing of $K_8$; any one of these would refute the corresponding characterization, as would a single non-simple drawing of $K_{4,7}$ satisfying 2-planarity.","tokens_in":32039,"feed_emoji":"📐","tokens_out":11627,"duration_ms":108842,"temperature":0.7,"pith_summary":"The paper confronts the question of which complete and complete bipartite graphs admit drawings that respect given beyond-planarity restrictions, such as every edge being crossed at most $k$ times, or no edge crossing two adjacent edges. Standard density arguments stop short at graphs like $K_8$ for 2-planarity or $K_{4,6}$ for 3-planarity, so the paper replaces combinatorics with a systematic enumeration: add one vertex at a time, insert its incident edges through every allowed pathway through the crossing structure, and discard drawings that are isomorphic to ones already seen. The headline result is an if-and-only-if statement: for a complete or complete bipartite input, the graph lies in the class exactly when the algorithm produces a valid drawing. Running this procedure yields tight cutoffs—for instance, $K_{a,b}$ with $a\\le b$ is 2-planar exactly for $a\\le 2$, or $a=3$ and $b\\le 10$, or $a=4$ and $b\\le 6$—and settles several open cases such as $K_8$ not being 2-planar and $K_{5,5}$ not being fan-planar.","feed_headline":"Exhaustive drawing search settles K4,7 and K5,5 are not 2-planar","feed_subtitle":"The same enumeration closes open cases across fan-planar, gap-planar, and fan-crossing-free classes.","key_machinery":"The mechanism is the half-pathway. In the planarization of a drawing, a half-pathway for a vertex $u$ is a path in the dual graph starting at a face incident to $u$ and ending at a destination face; inserting a new vertex $v$ there and drawing edge $(u,v)$ along that path crosses exactly the edges dual to the pathway. A pathway is the same but with the destination a face incident to an existing vertex, so it inserts an edge between two present vertices. The generation procedure builds every drawing by adding vertices one at a time, computing all valid half-pathways for the first new edge and all valid pathways for the remaining incident edges, while a prohibited-edges list keeps the drawing simple and within the class's crossing constraints. At each level it tests isomorphism via a face-boundary-walking bijection and deletes duplicates; this symmetry reduction is what makes exhaustive enumeration feasible.","core_discovery":"On the paper's own terms, the central discovery is that for complete and complete bipartite graphs, all topological representations belonging to a beyond-planarity class can be generated, up to isomorphism, by a vertex-by-vertex search. Each insertion is routed through valid half-pathways or pathways in the planarization of the current drawing; the search is pruned by maintaining forbidden crossing lists and by testing isomorphism at every step. Theorem 1 states that this generation is complete: for any such graph $G$ and any beyond-planarity class $C$ of topological graphs, $G$ belongs to $C$ if and only if the algorithm returns a valid drawing. The proof-of-concept applications give new tight characterizations, including that $K_8$ is not 2-planar, $K_9$ is not 3-planar, $K_{a,b}$ with $a\\le b$ is 3-planar if and only if $a\\le 2$, or $a=3$ and $b\\le 14$, or $a=4$ and $b\\le 9$, or $a=5$ and $b\\le 6$, and $K_{5,5}$ is not fan-planar. The paper also provides a combinatorial proof that $K_{a,b}$ is fan-crossing free if and only if $a\\le 2$ or ($a\\le 4$ and $b\\le 6$).","pith_inferences":["Beyond the paper, the same half-pathway enumeration should apply to any topological class whose forbidden configurations are local crossing constraints expressible on a planarization, so one could read off analogous cutoffs for other classes such as $k$-fan-bundle or crossing-angle constrained drawings.","The completeness of the enumeration is only as strong as the simple-drawing restriction; if a class's standard definition permits non-simple drawings, the paper's if-and-only-if characterizations may describe a stricter class, and the search would need to be rerun without that restriction.","The reported drawing counts, such as the 35 non-isomorphic 4-planar drawings of $K_9$, could serve as data for studying the typical crossing structure of extremal drawings or for testing conjectures about rotation systems of complete bipartite graphs.","A direct testable extension is to run the depth-first variant further on $K_{4,5}$ for the 4-planar and quasiplanar cases: a found certifying drawing would extend the paper's partial positive observations, while a proof of nonexistence would complete those characterizations."],"forward_implications":["The characterization of 2-planar complete bipartite graphs is now tight: $K_{a,b}$ is 2-planar exactly for $a\\le 2$, or $a=3$ and $b\\le 10$, or $a=4$ and $b\\le 6$, so $K_{4,7}$ and $K_{5,5}$ are not 2-planar.","$K_{5,5}$ is not fan-planar, settling the conjecture that it is not, and since $K_{5,5}$ is gap-planar while $K_{4,9}$ is fan-planar but not gap-planar, the gap-planar and fan-planar classes are incomparable.","$K_8$ is not 2-planar and $K_9$ is not 3-planar, so the chromatic number of 3-planar graphs is lower bounded by 8, with analogous lower bounds following for higher values of $k$.","The fan-crossing-free complete bipartite characterization is proven both combinatorially and by the implementation: $K_{a,b}$ is fan-crossing free if and only if $a\\le 2$ or $a\\le 4$ and $b\\le 6$.","For 4-planar and quasiplanar complete bipartite graphs, full enumeration becomes infeasible—$K_{4,4}$ alone already has tens of thousands of non-isomorphic drawings—so the paper reports only positive certificates obtained with a depth-first variant."],"supporting_citations":[{"why":"Supplies the base 1-planar characterizations that the $k$-planar cases extend, including the exact cutoffs for $K_n$ and $K_{a,b}$.","marker":"[20]"},{"why":"Provides the $k$-planar edge-density bound $5n-10$ used to rule out $K_9$ for 2-planar graphs and to frame the remaining gaps.","marker":"[39]"},{"why":"Shows $K_{3,b}$ is $k$-planar if and only if $b\\le 4k+2$, used for the $a=3$ rows of the complete bipartite $k$-planar characterizations.","marker":"[6]"},{"why":"Gives the bipartite fan-planar density bound $4n-12$ and frames the conjecture that $K_{5,5}$ is not fan-planar.","marker":"[7]"},{"why":"Provides the 2-planar and fan-planar drawing of $K_7$ used as the positive lower bound for complete graphs.","marker":"[13]"},{"why":"Proves $K_{4,b}$ is fan-planar for every $b$ and supplies the fan-planar density bound $5n-10$, anchoring the $a\\le 4$ side of the fan-planar characterization.","marker":"[33]"},{"why":"Proves the fan-crossing-free density bound $4n-8$ and that $K_7$ is not fan-crossing free, which combines with [20] for the complete-graph characterization.","marker":"[19]"},{"why":"Establishes the gap-planar characterizations for complete graphs and the base bipartite instances $K_{3,12}$, $K_{4,8}$, and $K_{5,6}$.","marker":"[11]"},{"why":"Refines gap-planar bipartite upper bounds to $K_{3,14}$, $K_{4,10}$, and $K_{6,6}$, which the paper extends by ruling out $K_{4,9}$.","marker":"[10]"},{"why":"Records the prior combinatorial proof that $K_{5,5}$ is not 2-planar, cited in the paper's table as the reference for that negative instance.","marker":"[34]"}],"fun_headline_variants":["Exhaustive drawing search settles beyond-planar bounds","All drawings enumerated to prove new graph limits","Beyond-planarity: exhaustive enumeration yields tight bounds","K_8, K_9 and more: exhaustive search closes cases","Algorithmic enumeration cracks beyond-planar graph classes"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that restricting to simple drawings is without loss of generality for every class considered and that the unverified implementation exhaustively enumerates every simple drawing; if a non-simple drawing belongs to a class, or the search misses one, the if-and-only-if characterizations collapse.","fun_headline_variants_meta":{"raw":{"variants":["Exhaustive drawing search settles beyond-planar bounds","All drawings enumerated to prove new graph limits","Beyond-planarity: exhaustive enumeration yields tight bounds","K_8, K_9 and more: exhaustive search closes cases","Algorithmic enumeration cracks beyond-planar graph classes"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000591,"raw_usage":{"total_tokens":2779,"prompt_tokens":959,"completion_tokens":1820,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":575,"completion_tokens_details":{"reasoning_tokens":1744}},"tokens_in":575,"tokens_out":1820,"duration_ms":13939,"temperature":1.0,"reasoning_tokens":1744,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T14:25:53.835203+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Find, by independent exhaustive enumeration or by construction, a simple 2-planar drawing of $K_{4,7}$ or $K_{5,5}$, a fan-planar drawing of $K_{5,5}$, or a 2-planar drawing of $K_8$; any one of these would refute the corresponding characterization, as would a single non-simple drawing of $K_{4,7}$ satisfying 2-planarity.","supporting_citations":[{"cited_title":"Combinatorica 17(3), 427–439 (1997)","cited_arxiv_id":null,"evidence_quote":"Provides the $k$-planar edge-density bound $5n-10$ used to rule out $K_9$ for 2-planar graphs and to frame the remaining gaps."},{"cited_title":"In: ISAAC","cited_arxiv_id":null,"evidence_quote":"Gives the bipartite fan-planar density bound $4n-12$ and frames the conjecture that $K_{5,5}$ is not fan-planar."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the 2-planar and fan-planar drawing of $K_7$ used as the positive lower bound for complete graphs."},{"cited_title":"Algorithmica 73(4), 673–695 (2015)","cited_arxiv_id":null,"evidence_quote":"Proves the fan-crossing-free density bound $4n-8$ and that $K_7$ is not fan-crossing free, which combines with [20] for the complete-graph characterization."},{"cited_title":"In: Biedl, T.C., Kerren, A","cited_arxiv_id":null,"evidence_quote":"Refines gap-planar bipartite upper bounds to $K_{3,14}$, $K_{4,10}$, and $K_{6,6}$, which the paper extends by ruling out $K_{4,9}$."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Records the prior combinatorial proof that $K_{5,5}$ is not 2-planar, cited in the paper's table as the reference for that negative instance."}],"review_version":1}