{"id":"6fbced1a-cda9-4f27-a098-be50593c4e29","arxiv_id":"2411.17565","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Outer-RAC graphs are planar and have at most 2.5n-4 edges, a bound that is tight, and low-degree series-parallel graphs admit linear-time outer-RAC drawings.","lead":"This paper studies straight-line graph drawings where every vertex lies on the outer boundary and every crossing is a right angle. It proves such graphs are always planar and sparse, and gives linear-time drawing algorithms for low-degree series-parallel graphs.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 1's proof rests on unproved Jordan-curve assertions: each block has a simple outline containing exactly its edges, and the outer boundary is a simple cycle through all vertices. Neither is established, and the copy/delete construction fails without them.","rationale":"The reader's weakest assumption correctly identifies the block-outline existence claim in Section 3 as the main unproved step. My read agrees but adds a second, equally load-bearing gap: the proof assumes a simple outer cycle C through all vertices, whereas the outer face boundary of an outer drawing with cut vertices is a closed walk, not a simple cycle. This makes the copy step undefined for exactly the non-biconnected graphs that the theorem claims to cover. The algorithmic sections (Theorems 6 and 7) are much more detailed, with explicit invariants and local constructions, and the lower-bound construction via chains of K4's is explicit and reproducible; those parts are not where the risk concentrates. The concern is a rigor gap, not a demonstrated counterexample: the result may well be true, and the missing outline lemma may be provable from the planarization of the drawing. For that reason the correct disposition remains conditional rather than reject. No formal verification or code is provided, so the computational check on small instances is a meaningful way to test whether the asserted geometric facts actually hold in the configurations the proof must handle.","tokens_in":22686,"tokens_out":10769,"duration_ms":161621,"concrete_test":"Perform an exhaustive enumeration of outer-RAC drawings for all graphs on n≤6 vertices (e.g., over all order types and slope assignments), and for each block B test the Section 3 construction: trace the alternating walk from the first endpoint of B and verify that it returns to the next endpoint of B, is simple, and encloses all B-edges and no non-B edges; also verify for non-biconnected inputs that a simple outer cycle C through all vertices exists. If any instance violates these, Theorem 1's proof is invalid as written; if all pass, promote the outline claim to a lemma with a formal proof.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim is Theorem 1: every outer-RAC graph is planar. The only proof is the block-outline/copy construction in Section 3. The construction is sound only if (i) there is a simple closed curve C that bounds the drawing and contains all vertices; (ii) every block B admits an outline O(B) that is a simple cycle, contains all edges of B and no edge outside B; and (iii) the outlines of different blocks do not cross and are compatible with deleting one slope set in one copy and the other slope set in the other copy. The paper asserts (ii) in a single sentence ('there necessarily exists a closed cycle O(B)...') without proof. The proposed alternating walk is not shown to be simple or even to terminate at v_{i+1}; for blocks whose crossing graph has cycles (e.g., a 4-cycle of crossings) this is exactly where a self-intersecting or non-enclosing walk can occur. Assertion (i) is also not automatic: for graphs with cut vertices the outer face boundary is a closed walk, not a simple cycle, so 'copy the interior of C to the outside' is undefined. Edges that do not cross are not explicitly assigned to a slope set, so after copying, a non-block edge survives twice unless treated as a degenerate block. These gaps are load-bearing because Theorem 2's density bound reuses the same outline machinery; the algorithmic sections and the explicit K4-chain lower bound are independent and do not compensate for the missing topological lemma.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper introduces outer-RAC and outer-apRAC drawings, in which all vertices are incident to the outer cell and all crossings are right-angled, with outer-apRAC additionally requiring all crossing edges to have slopes ±1. The main claim is that every outer-RAC graph is planar (Theorem 1) and has at most 2.5n−4 edges (Theorem 2), with the bound tight even for outer-apRAC graphs via a chain of K4's (Theorem 3). The paper also proves that K2,5 and the octahedral graph are not outer-RAC (Theorems 4 and 5), and gives linear-time algorithms for outer-apRAC drawings of subcubic biconnected series-parallel graphs (Theorem 6) and outer-RAC drawings of subquartic biconnected series-parallel graphs (Theorem 7).","tokens_in":120,"tokens_out":5428,"duration_ms":404533,"significance":"If the results are correct, the paper establishes a clean structural statement—outer-RAC graphs form a proper subfamily of planar graphs—together with a tight density bound and efficient drawing algorithms for natural bounded-degree series-parallel classes. The algorithmic sections are constructive and detailed, and the explicit lower-bound construction via K4-chains is a strength. However, the central topological claim rests on an unproved geometric lemma about block outlines, and the density proof inherits the same gap. The paper's significance is therefore conditional on repairing that lemma.","major_comments":[{"comment":"The existence of a closed cycle O(B) with the four stated properties is asserted in a single sentence: \"there necessarily exists a closed cycle O(B)\". The alternating-walk construction that follows is not proved to yield a simple cycle, to contain exactly the edges of B, or even to terminate at v_{i+1}; for blocks whose crossing graph contains a cycle of crossings, self-intersecting or non-enclosing walks are a real possibility. This outline lemma is the foundation of both Theorem 1 and Theorem 2, so it must be stated as a formal lemma and proved.","section":"Section 3, paragraph defining O(B)"},{"comment":"The copy/delete construction assumes that the outer boundary C is a simple cycle through all vertices and that \"the interior of C\" is well defined. For graphs with cut vertices, the outer face boundary is a closed walk rather than a simple cycle, so copying the interior of C to the outside is undefined. The proof also leaves implicit how edges that belong to no crossing block are treated: after copying, such edges appear twice, and the deletion step only mentions slope sets B1 and B2 of blocks. These points must be addressed explicitly for the planarization argument to be complete.","section":"Theorem 1"},{"comment":"The density proof in Appendix A inherits the unproved outline machinery. The claim that \"we can find a sequence of bounded blocks B0, B1, . . . , Bk\" such that each Bi shares a vertex or an edge with the preceding union requires that outlines of distinct blocks are non-crossing and that every block is enclosed by its outline; these are exactly the assertions missing from Section 3. Without a proof of the outline lemma, the decomposition argument and hence the bound m ≤ 2.5n − 4 are not fully justified.","section":"Theorem 2 / Appendix A"}],"minor_comments":[{"comment":"In the introduction, \"parameterited\" should be \"parameterized\".","section":"Section 1"},{"comment":"In the paragraph on SPQR-trees, \"SQPR-tree\" should be \"SPQR-tree\".","section":"Section 2"},{"comment":"The face-counting argument around Equations (1) and (2) is very dense; a short example illustrating the assignment of triangular faces to a face of length j would significantly improve readability.","section":"Section 3, Lemma 2"},{"comment":"The statement \"because T is triangular, it contains no two parallel bounding segments\" is cryptic; the intended argument is that a straight segment crossing two different sides of a right triangle cannot cross both at right angles, but this deserves one sentence of explanation.","section":"Section 4, Lemma 4"},{"comment":"The invariants I.1–I.7 are complex, and the proof that I.3–I.5 are maintained in the S-node boundary cases, especially k = 2, is only sketched; additional detail would help the reader verify the construction.","section":"Appendix C, Theorem 7"}],"recommendation":"major_revision","confidential_remarks":"The central issue is the missing proof of the block-outline lemma in Section 3. The algorithmic results and the counterexamples appear independent of that lemma and may be publishable on their own, but the headline claim that outer-RAC graphs are planar hinges on the outline construction. I would encourage a revision rather than rejection, since the gap seems repairable: the authors need to supply a formal Jordan-curve argument or a different proof strategy for Theorem 1."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The paper opens a genuinely new subarea—unrestricted outer-RAC drawings—and the headline claims are plausible. But the proof of the central theorem, that every outer-RAC graph is planar, rests on a geometric existence assertion that is stated in one sentence and never proved. The algorithmic parts are considerably more solid.\n\nWhat is new: Theorem 1 (planarity) and the tight density bound 2.5n-4 are new, as is the SPQR-tree drawing algorithm for subquartic SP-graphs. The obstruction examples (K2,5 and the octahedron) are simple and useful. The lower-bound construction via outer-1-planar graphs is a known route, and the authors credit it properly.\n\nThe soft spots are concentrated in Section 3. The outline O(B) of a block is introduced with \"there necessarily exists a closed cycle\" satisfying four properties; that is the load-bearing step, and it is not proved. The alternating walk along \"clockwise last\" edges is not shown to be simple or even to terminate at the next vertex. Blocks whose crossing graph contains a cycle are exactly where this can fail. The copy/delete construction then copies the interior of the outer cycle C to the outside, but when the drawing has cut vertices, C is only a closed walk, not a simple cycle, so \"copy the interior of C\" is undefined. Edges that belong to no block are not assigned to either slope set, so after copying they survive twice unless treated as degenerate blocks. These are not cosmetic issues: Theorem 2 reuses the same outline machinery, and Appendix A's sequence of bounded blocks is asserted rather than derived. Theorems 4 and 5 are one-line deductions from Lemma 4; those are probably fine but terse.\n\nWhat I trust: the algorithms in Section 5 and Appendix C come with invariants and case analysis; the density counting in Lemma 2 is explicit; the lower-bound construction is independent and clean. I do not think the main results are false—I think the paper is not yet referee-ready in its central proof.\n\nWho is this for: the graph drawing / beyond-planarity community will want to know these results, and the paper deserves a serious referee. My recommendation: send it to review, but require a complete proof of the outline lemma and a clean treatment of cut vertices and non-crossing edges before acceptance. I would not build on Theorem 1 until that lemma is written up.","headline":"Plausible and interesting results, but the main planarity proof rests on an unproved block-outline lemma; the algorithm sections are the strongest part.","tokens_in":23536,"tokens_out":3392,"would_cite":false,"duration_ms":33863,"reading_group":"maybe","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 proves that every outer-RAC graph is planar and that the class has a tight edge bound of $2.5n-4$.","keywords":["outer-RAC graphs","right-angle crossing drawings","planarity","edge density","series-parallel graphs","SPQR-tree","beyond planarity","axis-parallel RAC drawings"],"falsifier":"Try to draw $K_{3,3}$ with all six vertices on the outer cell and every crossing at a right angle: Theorem 1 predicts this is impossible, so any such drawing would directly refute the planarity claim.","tokens_in":22504,"feed_emoji":"📐","tokens_out":9928,"duration_ms":87178,"temperature":0.7,"pith_summary":"This paper studies graphs that can be drawn with all vertices on the outer cell and every crossing at a right angle, the outer-RAC model, plus an axis-parallel variant where crossing edges are horizontal and vertical. Its main claim is that such drawings never force a graph to be non-planar: every outer-RAC graph is planar, so the right-angle condition restricts geometry without expanding topology. The paper also proves that any such graph on $n$ vertices has at most $2.5n-4$ edges and that this density bound is tight, with matching examples even in the axis-parallel case. For low-degree series-parallel graphs it provides linear-time drawing algorithms, and it exhibits planar graphs of small degree that cannot be drawn this way. If correct, the result reframes outer-RAC drawings as a geometric drawing style for a strict subclass of planar graphs rather than a new class of non-planar graphs.","feed_headline":"Outer-RAC graphs are planar, with a tight 2.5n-4 edge bound","feed_subtitle":"If correct, outer-RAC graphs are always planar, and the 2.5n-4 edge limit is exact.","key_machinery":"The argument turns on two devices. First, the crossing graph of a drawing is partitioned into blocks, maximal connected sets of edges that cross each other, and each block is assigned a closed outline $O(B)$ that is assumed to contain exactly that block's edges and to separate them from everything else; the planarity proof copies the interior of the outer cycle to the exterior and removes one of the two perpendicular slope sets in each copy, so those outlines let the crossings disappear. Second, the algorithmic results use the SPQR-tree of a biconnected graph, a tree decomposition by separation pairs, and draw the skeleton of each node inside reserved regions $R(\\mu)$ so that a linear-time top-down traversal produces the required outer-(ap)RAC drawing.","core_discovery":"The paper's central claim is that right-angle crossings do not make a graph non-planar as long as all vertices lie on the outer cell. Theorem 1 states that every outer-RAC graph is planar; the proof partitions crossing edges into blocks, encloses each block in a closed outline $O(B)$, then copies the interior of the outer cycle to the exterior and deletes one slope set per copy to uncross all edges. The paper further establishes that outer-RAC graphs form a proper subset of planar graphs and have at most $2.5n-4$ edges, a bound that is tight even for the more restricted outer-apRAC class. It provides linear-time algorithms for drawing biconnected series-parallel graphs: outer-apRAC drawings for maximum degree 3 and outer-RAC drawings for maximum degree 4. It also gives non-outer-RAC examples among degree-5 series-parallel graphs and degree-4 triconnected planar graphs.","pith_inferences":["If the proof is right, the outer-RAC model is not a true 'beyond planar' class in the usual topological sense: right-angle crossings add geometric constraints without admitting any non-planar graphs, so future work should focus on which planar graphs admit such drawings.","A testable extension is to check whether every extremal outer-RAC graph with exactly $2.5n-4$ edges decomposes into $K_4$ blocks sharing edges, as Theorem 2's tight case suggests, which could lead to a structural characterization of the densest examples.","If the outline construction can be made fully rigorous, the same uncrossing idea may generalize to other outer drawing models where each block of crossing edges uses only two perpendicular slopes, potentially transferring the planarity conclusion to those models."],"forward_implications":["Non-planar graphs such as $K_5$ or $K_{3,3}$ cannot admit outer-RAC drawings, since Theorem 1 forces every outer-RAC graph to be planar.","Every outer-RAC graph on $n$ vertices has at most $2.5n-4$ edges, and the bound cannot be improved because there are infinitely many outer-apRAC graphs attaining it.","Biconnected series-parallel graphs of maximum degree 3 can be drawn outer-apRAC in linear time, and those of maximum degree 4 can be drawn outer-RAC in linear time.","Maximum degree alone is not sufficient for outer-RAC: there is a series-parallel graph of maximum degree 5 and a triconnected planar graph of maximum degree 4 that are not outer-RAC.","The $2.5n-4$ density bound distinguishes outer-RAC graphs from circular RAC drawings, which have a tight bound of $2n-2$ when all vertices must lie on a circle."],"supporting_citations":[{"why":"Establishes the RAC drawing model and its initial density and bend results, which this paper's outer-RAC variant extends.","marker":"[23]"},{"why":"Shows every outer-1-planar graph has a right-angle crossing drawing, which the paper uses to conclude its tight lower-bound examples are outer-RAC.","marker":"[17]"},{"why":"Provides an independent density lower bound for outer-1-planar graphs, used together with [8] to certify tightness of the $2.5n-4$ edge bound.","marker":"[22]"},{"why":"Gives the outer-1-planar graph density lower bound that supplies the matching construction for outer-apRAC graphs.","marker":"[8]"},{"why":"Linear-time SPQR-tree computation on which the drawing algorithms' $O(n)$ running time relies.","marker":"[31]"},{"why":"Introduces axis-parallel RAC (apRAC) drawings, the restricted variant that the paper studies and uses for the tight density examples.","marker":"[3]"}],"fun_headline_variants":["Outer-RAC graphs are planar: tight 2.5n-4 edge bound","Right-angle crossings keep graphs planar if outer","Outer-RAC graphs: planar, tight density bound","Outer-apRAC graphs also have 2.5n-4 max edges"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The planarity proof assumes that each block of crossing edges can be enclosed by a closed outline that contains exactly that block's edges and no others, and that these outlines never cross each other; this geometric fact is stated without proof.","fun_headline_variants_meta":{"raw":{"variants":["Outer-RAC graphs are planar: tight 2.5n-4 edge bound","Right-angle crossings keep graphs planar if outer","Outer-RAC graphs: planar, tight density bound","Outer-apRAC graphs also have 2.5n-4 max edges"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.0006,"raw_usage":{"total_tokens":2812,"prompt_tokens":963,"completion_tokens":1849,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":579,"completion_tokens_details":{"reasoning_tokens":1772}},"tokens_in":579,"tokens_out":1849,"duration_ms":13583,"temperature":1.0,"reasoning_tokens":1772,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T12:00:08.973989+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Try to draw $K_{3,3}$ with all six vertices on the outer cell and every crossing at a right angle: Theorem 1 predicts this is impossible, so any such drawing would directly refute the planarity claim.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Establishes the RAC drawing model and its initial density and bend results, which this paper's outer-RAC variant extends."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Shows every outer-1-planar graph has a right-angle crossing drawing, which the paper uses to conclude its tight lower-bound examples are outer-RAC."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides an independent density lower bound for outer-1-planar graphs, used together with [8] to certify tightness of the $2.5n-4$ edge bound."},{"cited_title":"In: Gørtz, I.L., Farach-Colton, M., Puglisi, S.J., Herman, G","cited_arxiv_id":null,"evidence_quote":"Introduces axis-parallel RAC (apRAC) drawings, the restricted variant that the paper studies and uses for the tight density examples."}],"review_version":1}