{"id":"fdc6989f-a38d-4f9f-8f43-5c4e1e07b7ad","arxiv_id":"1908.01981","paper_version":4,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Every outerplanar graph has a monotonic edge-intersection-of-paths-on-a-grid representation with at most two bends, and maximal outerplanar graphs and cacti are fully classified by forbidden induced subgraphs for bend numbers 0, 1, and 2.","lead":"This mathematics paper proves that every outerplanar graph can be drawn as an edge-intersection graph of monotonic paths on a grid with at most two bends, the first such bound for this restricted drawing model. It also classifies which maximal outerplanar graphs and cacti need 0, 1, or 2 bends and provides fast algorithms to build the drawings.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Algorithm 2.2's proof of Theorem 2.7 depends on an unformalized free-part invariant; Lemma 2.6 and Theorem 2.7(ii) rely on Figure 1 rather than a coordinate argument, leaving unintended intersections possible.","rationale":"Lemma 2.6's invariant is the exact spot where Theorem 2.7's no-unintended-intersection claim would fail if anything is wrong. The reader's weakest_assumption identifies this same spot, so I agree with the conditional verdict. The surrounding parts of the proof—the separation property, the path-separation lemma, and the green-tree arguments in Lemma 2.6(i)-(iii)—are worked out in detail and give real support. The weakness is localized: the geometric invariant (free parts ordered and clear) is asserted and illustrated rather than proved by induction with coordinates. Since the construction in Algorithm 2.2 is specified by the same figures, the argument is close to circular at that point. An exhaustive test on small outerplanar graphs is a practical way to look for a concrete counterexample; if none is found, the remaining issue is formalization, not a known false theorem. The internal typo in Corollary 5.11 (bend number 2 where Theorem 5.9 forces 1) is a separate proofreading issue for the cactus section and does not affect Theorem 2.7, but it reinforces the need for a careful revision.","tokens_in":39874,"tokens_out":10641,"duration_ms":120364,"concrete_test":"Write an exhaustive checker that runs Algorithm 2.2 (implemented directly from Figures 1(a)-(e) with explicit coordinates) on all connected outerplanar graphs with n <= 8 vertices, and verifies by brute force that the resulting path set is a Bm2-EPG representation: paths are monotone, have at most two bends, and intersect exactly on the edges of G. If any instance fails, Theorem 2.7 is false. If all pass, the concern is reduced to a formalization gap; to close that gap, one would additionally need a coordinate-level inductive proof of the free-part invariant, e.g. specifying Rv = [(xv,yv),(xv+Lv,yv)] and proving that each new vertical segment lies in the column interval between consecutive neighbors and above all existing rows.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim, Theorem 2.7 (every outerplanar graph has a Bm2-EPG representation), is proved by Algorithm 2.2. The correctness argument in Theorem 2.7(ii) relies on the assertion that each newly constructed path Pvij 'is contained in the free part Rvi of Pvi, where no other path has been constructed so far' and therefore cannot intersect any previously constructed path except Pvi and the intended neighbors. This assertion is the load-bearing point, and it is not proved. Lemma 2.6 states the needed invariant only informally: green paths have a free part Rv on their lower horizontal segment, ordered so that earlier green paths lie to the left and below later ones. The proof that the invariant is maintained is the sentence 'new paths are constructed in such a way that this property is maintained' and a reference to Figure 1. But the paths in Figures 1(a)-1(e) are two-bend monotone paths; they are not contained in the segment Rvi. Only their lower horizontal segment is placed there. Their vertical segment and upper horizontal segment extend into the region above and to the right of Rvi, and no argument shows that this region has been kept free of previously drawn red paths or of other green paths' upper segments. Because the construction rules are themselves specified by the same figures, the proof of the key non-intersection property is essentially an appeal to the construction. If the invariant fails for some labeling or graph, the drawing would have unintended adjacencies and Theorem 2.7 would be false for that input. The surrounding path-separation arguments in Lemma 2.6 are detailed, so the gap is localized to this geometric invariant, but it is exactly the point on which the central claim depends.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies the (monotonic) bend number of outerplanar graphs, i.e., the minimum number of bends needed to represent a graph as an edge intersection graph of monotone paths on a grid. Its main theorem (Theorem 2.7) claims that every outerplanar graph is in Bm2, and it gives an algorithmic construction (Algorithm 2.2). For maximal outerplanar graphs, the paper characterizes membership in B0 (equivalently Bm1) by absence of S3, and membership in B1 by the absence of the induced configurations M1 and Mℓ1 in the reduced graph (Theorem 4.26); it also provides polynomial-time algorithms for these cases. For cacti, Theorem 5.9 claims that every cactus is in Bm1, and Theorem 5.7 characterizes those in B0 as the MC-free cacti. The paper concludes with a summary and open problems. The proofs are constructive and a number of subroutines are supplied as explicit algorithms.","tokens_in":40173,"tokens_out":5714,"duration_ms":54859,"significance":"If the results are correct, the paper makes a substantial contribution: it strengthens the known upper bound of 2 on the bend number of outerplanar graphs to the monotone setting, and it gives forbidden-induced-subgraph characterizations together with polynomial-time construction algorithms for two natural subclasses. The constructive nature of the proofs and the explicit algorithms are valuable, and the paper places its results well within the existing literature on EPG representations. However, the correctness of the central construction in Section 2 currently rests on an informal free-part invariant, and the cactus characterization in Section 5 contains a direct contradiction with Theorem 5.9. These issues affect load-bearing statements and must be resolved before the paper can be accepted.","major_comments":[{"comment":"The correctness proof of Algorithm 2.2 depends on the assertion that each newly constructed path is contained in the free part Rvi of Pvi, where no other path has been constructed so far. This assertion is false as stated: the new two-bend monotone paths shown in Figure 1 have only their lower horizontal segment inside Rvi; their vertical segment and upper horizontal segment extend into the region above and to the right of Rvi. The proof of Lemma 2.6 asserts that the free-part invariant is maintained, but the only justification is the sentence 'new paths are constructed in such a way that this property is maintained' together with a reference to Figure 1. No coordinate-based or inductive argument shows that the parts of the new paths lying outside Rvi avoid previously constructed red paths or the upper segments of earlier green paths. Since this is exactly the property that rules out unintended intersections, Theorem 2.7(ii) is not fully proved. The gap is fixable, but the invariant and the placement of full paths must be formalized.","section":"Section 2, Lemma 2.6 and Theorem 2.7(ii)"},{"comment":"Corollary 5.11 states that for a cactus G, b(G) = bm(G) = 2 when G is not MC-free. This directly contradicts Theorem 5.9, which proves that every cactus belongs to Bm1 and hence has bm(G) ≤ 1. The concluding paragraph of Section 6 also states the correct value, namely 'Otherwise b(G)=bm(G)=1 holds'. Thus the value 2 in Corollary 5.11 is a substantive error in a stated theorem and must be corrected to 1. In addition, the abstract's phrase 'the cacti with (monotonic) bend number equal to 0, 1 and 2' is misleading, because by Theorem 5.9 no cactus has bend number 2; the cactus characterization should refer to bend numbers 0 and 1 only.","section":"Section 5, Corollary 5.11"}],"minor_comments":[{"comment":"The abstract and the concluding summary claim characterizations for cacti with bend number 0, 1 and 2, but the paper proves that cacti have bend number at most 1; please adjust the wording to '0 and 1' for the cactus case.","section":"Abstract and Section 6"},{"comment":"There is a typo in the sentence 'For cacti the monotonic bend number and the bend number coincide and are bounded by 1, i.e. and b(G)=bm1(G)≤1 holds for every cactus G.' The expression 'bm1' should be 'bm(G)'.","section":"Section 6, summary paragraph"},{"comment":"The description 'the straight line segment of the edge {v0, vi} rotates counterclockwise around v0' is slightly imprecise; it is the ray from v0 through the vertex vi that rotates around v0. Please rephrase for clarity.","section":"Algorithm 2.1, line 8"},{"comment":"The proof relies heavily on Figure 1 for the placement of full paths and free parts; since this figure is the only justification for a key invariant, the authors should either add explicit coordinate descriptions or a formal inductive invariant so that the construction is machine-checkable.","section":"Lemma 2.6, proof"}],"recommendation":"major_revision","confidential_remarks":"The contradiction in Corollary 5.11 appears to be a typographical error that can be fixed by replacing 2 with 1, and the concluding summary already uses the correct value. The more serious issue is the unformalized free-part invariant in Section 2; although the construction is plausible and likely correct, the proof as written does not meet the standard of rigor expected for a journal publication. I would encourage the authors to provide a formalized invariant and a coordinate-based verification of the non-intersection property. The rest of the paper, including the forbidden-subgraph characterizations and algorithms, is well structured and appears sound."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"First thing you should know: this paper proves that every outerplanar graph is in Bm2, the monotonic version of the two-bend EPG class. That is genuinely new; the non-monotonic bound was known from Heldt–Knauer–Ueckerdt, but the monotonic version was open. The paper also gives the first forbidden-subgraph characterizations for maximal outerplanar graphs and cacti by bend number, with polynomial-time construction algorithms. The constructive proofs are real: the algorithms actually output representations with the claimed number of bends, and the n-sun analysis is clean.\n\nCredit where due: the reduction to the almost-dual tree for maximal outerplanar graphs is well executed, and the cactus construction in Theorem 5.9 is a nice piece of work. The authors are also honest about what they import from earlier papers; the lower bounds come from properly cited external results, and there are no fitted parameters.\n\nSoft spots, in order of seriousness. First, the proof of Theorem 2.7 via Algorithm 2.2 has a genuine gap. Lemma 2.6 asserts that each new path is contained in a free part of the current path where no other path has been constructed, but the invariant is justified mainly by Figure 1. The stress-test note is right: the drawn two-bend paths extend above and to the right of the free segment, and no argument shows that region stays clear of earlier red or green paths. This is the load-bearing point for the non-intersection property. I do not think the claim is false—the construction looks plausible and the rest of the proof is detailed—but a referee should ask for a coordinate-based induction instead of a figure.\n\nSecond, Corollary 5.11 says a non-MC-free cactus has bend number 2, which directly contradicts Theorem 5.9, where every cactus is shown to be in Bm1. The concluding summary in Section 6 says 1, so this is almost certainly a typo, but it is the displayed corollary that people will quote. That needs fixing before publication.\n\nMinor: the running-time claims for the cactus algorithms look right but are stated with a somewhat heavy data structure; not a flaw, just worth checking.\n\nBottom line: this deserves a serious referee. The main result is likely correct, the characterizations are useful, and the flaws are fixable. I would send it to review and ask for a revision that formalizes the free-part invariant and corrects Corollary 5.11. If you work on EPG representations, cite it; if you run a reading group, it is a reasonable maybe.","headline":"New bound for outerplanar monotonic EPG representations, with fixable gaps: the main construction is plausible but under-formalized, and one corollary contradicts an earlier theorem.","tokens_in":40771,"tokens_out":2027,"would_cite":true,"duration_ms":24123,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C62","05C10","05C75"],"pacs":[],"model":"deepseek-v4-flash","headline":"Every outerplanar graph has a monotonic EPG representation with at most two bends.","keywords":["EPG representation","monotonic paths on a grid","bend number","outerplanar graphs","maximal outerplanar graphs","cacti","forbidden induced subgraphs","intersection graphs"],"falsifier":"Implement Algorithm 2.2 and check, for every exploration step, that the free part $R_{v_i}$ is clear of previously constructed paths; the first violation is a concrete counterexample to Lemma 2.6 and hence to Theorem 2.7. More directly, any outerplanar graph whose monotonic bend number exceeds 2 would refute the theorem.","tokens_in":39667,"feed_emoji":"📐","tokens_out":8029,"duration_ms":70853,"temperature":0.7,"pith_summary":"The paper proves that every outerplanar graph—a graph whose vertices can all be placed on the outer face of a drawing—can be represented as edge intersections of monotonic paths on a grid, with each path turning at most twice. It then pins down the exact minimum bend count for two important subclasses: maximal outerplanar graphs have monotonic bend number 0 or 2, while cacti have bend number 0 or 1. All proofs are constructive and the representations are built in polynomial time.","feed_headline":"Outerplanar graphs draw with two monotonic bends","feed_subtitle":"The paper proves the bound is tight and computes exact bend numbers for maximal outerplanar graphs and cacti.","key_machinery":"The central device is the free part $R_v$ of an already-drawn path $P_v$, an unused stretch of its lower horizontal segment where Algorithm 2.2 places every newly constructed path. A 'nice labeling' orders the vertices counterclockwise around an added universal vertex, and this ordering has a separation property that keeps the free parts disjoint until they are used, ensuring that new paths intersect exactly the paths they are meant to intersect. The characterizations rest on two auxiliary graphs: the almost-dual graph (the tree formed by the triangular faces of a maximal outerplanar graph) and the reduced graph (the graph obtained by keeping only the vertices and edges that belong to copies of $S_3$).","core_discovery":"The paper's central theorem, Theorem 2.7, states that every outerplanar graph lies in $B_2^m$: there is a grid drawing in which each vertex is a monotonic path (ascending in both rows and columns) with at most two bends, and two paths share a grid edge exactly when the corresponding vertices are adjacent. The proof is algorithmic: Algorithm 2.2 constructs such a representation in linear time from a 'nice labeling' of the vertices. For maximal outerplanar graphs, the paper characterizes the (monotonic) bend number by forbidden induced subgraphs—$S_3$ for monotonic bend number 0, and $M_1$ or $M_1^\\ell$ in the reduced graph for ordinary bend number 1. For cacti, it shows the bend number never exceeds 1 and is 0 exactly when the cactus avoids $M_2$, $M_3$, and cycles of length at least 4.","pith_inferences":["If the free-part invariant of Algorithm 2.2 were formalized as an explicit algebraic condition, it might extend the same two-bend monotonic construction to all graphs of treewidth at most 2, where the monotonic bend number remains open.","The contrast between maximal outerplanar graphs (monotonic bend number jumps from 0 to 2) and cacti (never above 1) suggests that a single triangle surrounded by other triangles, not just the presence of cycles, is what forces two monotonic bends.","A computational check on all small outerplanar graphs could empirically test the invariant; the first unintended overlap would pinpoint a gap in the proof of Lemma 2.6."],"forward_implications":["Every outerplanar graph has monotonic bend number at most 2, and the bound is best possible.","A maximal outerplanar graph has monotonic bend number 0 exactly when it contains no induced $S_3$; otherwise its monotonic bend number is 2.","A maximal outerplanar graph has ordinary bend number 1 exactly when its reduced graph is M-free.","Every cactus has monotonic bend number at most 1, and it is 0 exactly when it is $MC$-free.","All these representations can be constructed in polynomial time: linear for outerplanar graphs, quadratic for maximal outerplanar graphs with bend number 1."],"supporting_citations":[{"why":"Introduced EPG representations and supplied the edge-clique/claw-clique lemma used in the B1 characterization.","marker":"[23]"},{"why":"Provided an outerplanar graph with bend number 2, showing the upper bound is best possible.","marker":"[6]"},{"why":"Proved that every outerplanar graph is in B2, the result the paper strengthens to the monotonic setting.","marker":"[25]"},{"why":"Supplied the characterization of outerplanar graphs via adding a universal vertex, on which the nice labeling algorithm relies.","marker":"[18]"},{"why":"Showed that S3 is not in Bm1, a key lower bound in the maximal outerplanar graph characterization.","marker":"[14]"}],"fun_headline_variants":["Two bends suffice for monotonic grid paths of outerplanar graphs","Outerplanar graphs fit monotonic paths with at most two bends","Every outerplanar graph has a 2-bend monotonic grid representation","Outerplanar graphs: monotonic bend number at most 2","Monotonic EPG: outerplanar bound is two, with characterizations"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The main algorithm's correctness rests on a geometric invariant: the free part of each already-drawn path stays untouched until the moment it is used, so new paths touch only the paths they are meant to touch.","fun_headline_variants_meta":{"raw":{"variants":["Two bends suffice for monotonic grid paths of outerplanar graphs","Outerplanar graphs fit monotonic paths with at most two bends","Every outerplanar graph has a 2-bend monotonic grid representation","Outerplanar graphs: monotonic bend number at most 2","Monotonic EPG: outerplanar bound is two, with characterizations"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000627,"raw_usage":{"total_tokens":2924,"prompt_tokens":996,"completion_tokens":1928,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":612,"completion_tokens_details":{"reasoning_tokens":1830}},"tokens_in":612,"tokens_out":1928,"duration_ms":13758,"temperature":1.0,"reasoning_tokens":1830,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T14:56:57.538336+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Implement Algorithm 2.2 and check, for every exploration step, that the free part $R_{v_i}$ is clear of previously constructed paths; the first violation is a concrete counterexample to Lemma 2.6 and hence to Theorem 2.7. More directly, any outerplanar graph whose monotonic bend number exceeds 2 would refute the theorem.","supporting_citations":[{"cited_title":"3, 130–138","cited_arxiv_id":null,"evidence_quote":"Introduced EPG representations and supplied the edge-clique/claw-clique lemma used in the B1 characterization."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provided an outerplanar graph with bend number 2, showing the upper bound is best possible."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Proved that every outerplanar graph is in B2, the result the paper strengthens to the monotonic setting."},{"cited_title":"Vieweg & Sohn, Wiesbaden, 2004, Som e chap- ters from combinatorial geometry","cited_arxiv_id":null,"evidence_quote":"Supplied the characterization of outerplanar graphs via adding a universal vertex, on which the nice labeling algorithm relies."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Showed that S3 is not in Bm1, a key lower bound in the maximal outerplanar graph characterization."}],"review_version":1}