{"id":"1954273d-01e6-46cb-902f-5e3a298a26f2","arxiv_id":"1908.05345","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Strict confluent graphs are placed inside string graphs, unit interval graphs inside strict confluent graphs, strict bipartite outerconfluent graphs are exactly the domino-free bipartite permutation graphs, and strict outerconfluent graphs have cop number two.","lead":"This paper studies drawings where edges are bundled into shared smooth paths through junctions, and compares the graphs that admit such drawings with familiar graph families. It also shows these graphs can always be guarded by two cops and gives an exact description of one bipartite subclass.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 3's proof uses Δ-junctions, which lie outside the strict binary-junction model of Section 2; without a decomposition argument, the unit-interval-to-SC inclusion is unproven as stated.","rationale":"The reader's weakest assumption identifies exactly the same spot: Theorem 3's construction uses Δ-junctions, which the paper's own Section 2 and Section 7 treat as outside the strict binary-junction model. This is an internal-model inconsistency rather than a disagreement with external consensus, and it is load-bearing because Theorem 3 is one of the headline inclusions advertised in the abstract and in Figure 1. The proof in Appendix B is short and refers to Δ-junctions more than once, and the final claim that the drawing is strict is asserted without addressing the junction type. No formal verification or code is provided, so the gap is not closed elsewhere. At the same time, the concern is about the proof of a true-looking inclusion, not about the falsity of the theorem: K5 is known to be strict confluent, and the clique-based idea is plausible. Therefore the appropriate verdict remains CONDITIONAL, matching the reader's assessment. The other main contributions, especially Theorem 5's exact characterization and Theorems 6 and 7, are substantially independent of Theorem 3, so the gap does not by itself warrant rejection of the paper.","tokens_in":22786,"tokens_out":13693,"duration_ms":149072,"concrete_test":"Take the smallest nontrivial case of the Theorem 3 construction, for example the five-vertex clique K5 drawn with the d_i chain, and attempt to replace every Δ-junction by a network of binary merge/split junctions while preserving the same node order, the same represented graph, and the same incident-arc smooth connections. Systematically check whether any pair of nodes receives two distinct smooth paths or whether any self-loop appears. If such a replacement exists for K5, repeat the test on a unit-interval graph requiring inter-clique edges, such as the graph in Figure 4; if the replacement cannot be completed without creating duplicate paths or self-loops, the proof of Theorem 3 is invalid as stated.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The most load-bearing gap is in the proof of Theorem 3 (Appendix B). The construction draws each clique using Δ-junctions d_i, which are described as smoothly linking each pair of the three incident arcs. But Section 2 defines junctions for strict confluent diagrams as binary merge/split junctions with exactly one smooth pair, and Section 7 explicitly introduces Δ-junctions as an additional junction type for the separate tree-like Δ-SOC model. No argument is given that a Δ-junction can be expanded into binary junctions while preserving the exact set of smooth paths and the uniqueness condition required for strictness. A binary junction has only one smooth pair, so at least two of the three pairwise connections of a Δ-junction must be routed through additional junctions; any such routing risks creating a second smooth path for the third pair or introducing a self-loop. Since the proof of Theorem 3 relies essentially on these Δ-junctions for the clique layouts, the claimed inclusion unit-interval ⊆ SC is not established in the paper's own model. The theorem may well be true, and other contributions such as Theorems 5, 6, and 7 are not directly affected, but this proof needs either a decomposition lemma or a revised construction using only binary junctions.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies strict confluent (SC) and strict outerconfluent (SOC) graph drawings, in which edges are represented by unique smooth paths through a planar system of arcs and junctions. The main contributions are: (1) every SC graph is a string graph and every SOC graph is an outer-string graph (Theorems 1 and 2); (2) every unit-interval graph admits an SC drawing (Theorem 3); (3) the strict bipartite-outerconfluent graphs are exactly the domino-free bipartite permutation graphs (Theorem 5); (4) SOC graphs have cop number two (Theorem 6); and (5) tree-like Δ-SOC graphs have clique-width at most 16 (Theorem 7). The appendix also contains incomparability results between SOC graphs and several other graph classes. The paper is well structured, with detailed appendix proofs for most theorems, and it provides explicit geometric constructions for several of the inclusions.","tokens_in":23017,"tokens_out":6657,"duration_ms":69664,"significance":"If the results hold, the paper gives the first exact characterization of a natural strict outerconfluent graph class and establishes useful algorithmic and structural consequences, particularly the clique-width bound for tree-like Δ-SOC graphs and the cop-number result. The inclusions placing SC and SOC graphs inside string and outer-string graph families are also valuable for future work on recognition and on the relationship to intersection graph classes. The paper's strength lies in its concrete constructions and in the breadth of the graph-class comparisons in Appendix E. The main caveat is that the proof of Theorem 3 uses a junction type that is not part of the strict confluent model as defined in Section 2, and this issue directly affects the paper's central inclusion claim for unit-interval graphs.","major_comments":[{"comment":"The construction of strict confluent diagrams for unit-interval graphs uses Δ-junctions d_i (Appendix B, paragraph beginning 'We draw each clique Ci'), where each Δ-junction 'smoothly links each pair of the three incident arcs.' However, Section 2 defines a junction for strict confluent diagrams as a binary junction with exactly one smooth pair, and Section 7 explicitly introduces Δ-junctions as an additional junction type for a separate tree-like Δ-SOC model. The proof gives no argument that a Δ-junction can be expanded into binary junctions while preserving the exact set of smooth paths and the uniqueness requirement of strictness. Since the clique layout is the core of the construction, the claimed inclusion unit-interval ⊆ SC is not established in the paper's own model unless such a decomposition lemma is supplied or the construction is reworked with binary junctions only.","section":"Section 4 / Appendix B, Theorem 3"},{"comment":"The induction for the clique-width bound relies on the region-decomposition claim that 'all vertices of group D have precisely the same neighborhood outside of R' and on the assertion that 'at most one vertex, denoted s, in VR3 has two neighbors outside of VR3.' These statements are load-bearing for the 16-expression construction, but they are asserted without proof; the preceding observation that such vertices 'must all have a path to j which forms a smooth curve' does not by itself imply equality of outside neighborhoods. Please provide a formal argument, or weaken the construction accordingly.","section":"Appendix F, Theorem 9 (Section 7)"},{"comment":"The proof of Lemma 2 is too terse at a load-bearing point: the 'minimal distinct sub-paths p′ and q′ between two junctions i,j' are not defined formally, and the claim that following the arcs of the two merge-split pairs yields four nodes that together with u and v form a domino subgraph is asserted rather than demonstrated. Since Theorem 5 depends on Lemma 2, this case analysis should be expanded.","section":"Appendix C, Lemma 2"}],"minor_comments":[{"comment":"The sentence 'A (strict) confluent diagram with higher-degree junctions can easily be transformed into an equivalent (strict) one with only binary junctions' is later invoked implicitly, but Δ-junctions are degree-three junctions with three smooth pairs. Please state explicitly whether the transformation applies to Δ-junctions and give a proof or reference.","section":"Section 2"},{"comment":"The proof for co-comparability graphs says that a graph is 'verified to not be SOC by exhaustively searching all orders for represented crossings'; the search is not described, so the statement is not independently checkable. Please provide details or a reference.","section":"Appendix E, Theorem 8"},{"comment":"The legend refers to 'red, dashed boxes', 'orange boxes', and 'blue boxes', which are not distinguishable in black-and-white print; consider adding symbols or patterns.","section":"Figure 1"}],"recommendation":"major_revision","confidential_remarks":"The delta-junction issue in Theorem 3 is the main substantive obstacle. If the authors provide a decomposition lemma for Δ-junctions into binary junctions, or revise the construction to use only binary junctions, I would be inclined to support acceptance. I see no concerns about novelty or citation practice."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The paper gives the first real structural map of strict (outer-)confluent graphs. The inclusions into string and outer-string graphs, the exact bipartite characterization, cop number two for SOC graphs, and the clique-width bound for tree-like Δ-SOC graphs are all new and worth knowing.\n\nThe trace construction in Section 3 is genuinely clever: turning junction trees into strings is a neat way to prove SC ⊂ string and SOC ⊂ outer-string. Theorem 5, characterizing strict bipartite-outerconfluent graphs as exactly the bipartite permutation graphs that are domino-free, is a clean completion of Hui et al.'s earlier theorem. The cop number proof is careful and the lemmas about locking intervals seem to work. Theorem 7 is a substantial technical effort—the 16-expression construction is intricate and the region/depth decomposition looks coherent.\n\nThe main soft spot is Theorem 3. In Appendix B, the proof draws each clique using Δ-junctions, where a Δ-junction smoothly links each pair of three incident arcs. But Section 2 defines strict confluent diagrams with binary junctions and says higher-degree junctions can be transformed into binary ones; Section 7 introduces Δ-junctions as an additional junction type for a separate tree-like Δ-SOC model. The proof of Theorem 3 never explains how a Δ-junction can be expanded into binary junctions without losing strictness or creating extra smooth paths. This is a genuine gap, not a cosmetic issue: the claimed inclusion unit-interval ⊆ SC is not established in the paper's own model. It may well be fixable—a small binary gadget could simulate the three-way smooth connection—but that needs to be written down. The gap is localized: Theorems 1, 2, 5, 6, and 7 are not affected, since Theorem 7 explicitly allows Δ-junctions.\n\nThe other lesser issue is that some proofs are sketches, especially Theorem 7, but the sketches give enough detail for a specialist to fill in the missing steps. The non-inclusion results in Appendix E are a useful service. Citation patterns look fine; the paper builds on prior work without circularity.\n\nOverall: worth refereeing seriously. The verdict should be conditional on fixing Theorem 3. I'd send it to a strong graph drawing or structural graph theory referee, and ask for a decomposition lemma for Δ-junctions or a revised construction using only binary junctions. If that lands, the paper will be a solid contribution.","headline":"First substantial structural results for strict (outer-)confluent graphs, but the unit-interval inclusion has a definitional gap with Δ-junctions that needs patching.","tokens_in":23545,"tokens_out":1891,"would_cite":true,"duration_ms":19831,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C62","05C75","68R10","68U05"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper places strict confluent graphs inside string graphs and unit-interval graphs inside strict confluent graphs.","keywords":["strict confluent graphs","strict outerconfluent graphs","string graphs","outer-string graphs","unit-interval graphs","bipartite permutation graphs","clique-width","cop number"],"falsifier":"Inspect the clique gadget in the proof of Theorem 3: for a clique of three vertices, the three incident arcs meet smoothly at a $\\Delta$-junction. Check whether this gadget can be converted into a sequence of binary merge/split junctions while preserving the property that each pair of vertices has exactly one smooth path. If no such conversion exists for some unit-interval graph (for instance, the smallest graph whose construction requires a $\\Delta$-junction), then the claimed inclusion of unit-interval graphs into SC would not be supported by the paper's construction, and one should search for a concrete unit-interval graph that admits no strict confluent drawing.","tokens_in":22604,"feed_emoji":"📐","tokens_out":9532,"duration_ms":83571,"temperature":0.7,"pith_summary":"This paper studies strict confluent graph drawings, in which edges are not drawn as individual curves but as unique smooth paths through a planar network of junctions and arcs. It establishes that the class of strict confluent (SC) graphs is contained in the class of string graphs, and the class of strict outerconfluent (SOC) graphs is contained in the class of outer-string graphs. Conversely, it shows that every unit-interval graph has a strict confluent drawing. It also gives the first exact characterization of a natural strict outerconfluent class: the strict bipartite-outerconfluent graphs are exactly the domino-free bipartite permutation graphs. On the algorithmic side, the paper proves that SOC graphs have cop number at most two and that tree-like strict outerconfluent drawings with $\\Delta$-junctions have clique-width at most 16, making these graphs accessible to algorithms for bounded clique-width and to cops-and-robbers analysis.","feed_headline":"Unit-interval graphs are strict confluent","feed_subtitle":"A new chain of inclusions ties unit-interval graphs to strict confluent and string graphs.","key_machinery":"The central objects are junction trees and traces. For each vertex $u$, the junction tree $T_u$ has root $u$, leaves at the neighbors of $u$, and internal vertices at the junctions on the unique $uv$-paths; strictness makes this a tree. The trace $t(u)$ is a single curve obtained by a left-first DFS traversal of $T_u$, with U-turns at leaves and rerouting at shared merge-junctions; traces intersect if and only if the corresponding vertices are adjacent. This carries Theorems 1 and 2. For Theorem 3, the key gadget is a clique layout using $\\Delta$-junctions and split-junctions that route arcs between consecutive cliques across a line $H$ to invert order. For Theorem 5, the mechanism is the merge-split pair and the observation that in the cyclic order every crossing must be representable as part of a $K_{2,2}$; non-representable crossings in alternating $K_{3,3}$ order and in domino order are the obstructions. For Theorem 6, the central object is the node interval $N[u,v]$ between two vertices on the outer face, together with extremal pairs that allow cops to shrink the robber's locked interval. For Theorem 7, the mechanism is a region decomposition of the outer face: each region is outerplanar (clique-width at most 5), and the regions are glued together by a 16-expression using special labels for border vertices.","core_discovery":"The paper claims that strict confluent graphs form a subclass of string graphs (Theorem 1) and strict outerconfluent graphs form a subclass of outer-string graphs (Theorem 2). The mechanism is a tracing argument: from each vertex, one follows its junction tree and lays out a single curve that intersects another trace exactly when the two vertices are adjacent. The paper also claims that unit-interval graphs are strict confluent (Theorem 3), via a decomposition into cliques of consecutive intervals and explicit confluent gadgets for edges between neighboring cliques. For the outerconfluent setting, the paper claims that the class of strict bipartite-outerconfluent graphs equals the class of bipartite permutation graphs that are domino-free (Theorem 5), thereby giving the first exact characterization of a strict outerconfluent graph class; the proof shows that any non-strict bipartite outerconfluent drawing forces a chorded 6-cycle, which in a bipartite permutation graph is a $K_{3,3}$ (minus an edge) that can be redrawn strictly, and conversely that the domino obstruction is the only obstacle. Finally, the paper claims that every strict outerconfluent graph has cop number at most two (Theorem 6) by an interval-shrinking argument on the cyclic order of vertices, and that tree-like strict outerconfluent drawings with $\\Delta$-junctions have clique-width at most 16 (Theorem 7) by a decomposition into regions that each have clique-width at most 5, combined using labeled expressions.","pith_inferences":["The trace construction in Section 3 uses strictness mainly to ensure junction trees are trees; for non-strict confluent drawings, a similar construction might produce intersection representations by multi-curves or families of curves, possibly placing all confluent graphs inside a known intersection class such as multistring graphs.","The interval-shrinking proof of the cop-number bound may be adaptable to show that SOC graphs are contained in interval-filament graphs, a question the authors leave open; if so, SOC graphs would inherit further algorithmic and structural properties of that class.","The exact characterization of strict bipartite-outerconfluent graphs suggests a route toward a full characterization of all SOC graphs: the domino and alternating-$K_{3,3}$ obstructions could serve as the seeds of a split-decomposition or modular-decomposition tree characterization, which the authors mention as a promising but unexplored direction.","The clique-width bound of 16 is likely not tight: the constant arises from a generic labeling lemma applied to outerplanar regions, and a finer analysis of how regions interact at junctions could lower the bound or identify which labels can be reused."],"forward_implications":["Every unit-interval graph inherits all properties of strict confluent graphs, and every strict confluent graph inherits all properties of string graphs; in particular, any lower bound or algorithmic result known for string graphs applies to these classes.","The exact equality of strict bipartite-outerconfluent graphs with domino-free bipartite permutation graphs means this class is polynomial-time recognizable: one can compute a bipartite permutation representation and test the domino-free condition.","The cop-number bound of at most two puts SOC graphs on the same footing as interval-filament graphs among subclasses of outer-string graphs, and suggests that a single additional structural property separates them.","The clique-width bound of 16 for tree-like $\\Delta$-SOC graphs makes these graphs amenable to fixed-parameter algorithms and to meta-theorems for problems expressible in monadic second-order logic on graphs.","The non-inclusion results for circle, circular-arc, chordal, co-chordal, comparability, co-comparability, series-parallel, and pseudo-split graphs show that SOC graphs do not collapse into any of these standard families, so they form a genuinely new intersection-related class."],"supporting_citations":[{"why":"Defines strict confluent and strict outerconfluent drawings, including the binary merge/split junction model and the earlier SOC testing algorithm that this paper builds on.","marker":"[14]"},{"why":"Supplies Theorem 4, that bipartite-outerconfluent graphs equal bipartite permutation graphs, which Theorem 5 extends to the strict setting.","marker":"[32]"},{"why":"Introduced $\\Delta$-confluent drawings and proved tree-like $\\Delta$-confluent graphs are distance-hereditary; Theorem 7 generalizes this to tree-like $\\Delta$-SOC graphs with a clique-width bound.","marker":"[12]"},{"why":"Established cop-number bounds for outer-string graphs and other intersection classes, providing the baseline against which Theorem 6's cop number two is measured.","marker":"[19]"},{"why":"Provides the definitions of string graphs and outer-string graphs, the target superclasses in Theorems 1 and 2.","marker":"[34]"},{"why":"Supplies the clique-width framework and the algorithmic meta-theorems that make the bounded clique-width result in Theorem 7 significant.","marker":"[7]"},{"why":"Introduced confluent drawings and showed some graphs admit no confluent drawing; its obstruction examples are used in Appendix E for incomparability results.","marker":"[9]"}],"fun_headline_variants":["Strict confluent graphs are string graphs","Strict outerconfluent graphs are outer-string graphs","Unit-interval graphs are strict confluent","Strict outerconfluent graphs have cop number two","Domino-free bipartite permutation graphs are strict outerconfluent"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The proof that every unit-interval graph is strict confluent uses three-way junctions that smoothly connect three arcs; the paper's official definition of strict confluent drawings allows only binary merge/split junctions, and no argument is given that these three-way junctions can be replaced by binary ones without creating two smooth paths between some pair of vertices.","fun_headline_variants_meta":{"raw":{"variants":["Strict confluent graphs are string graphs","Strict outerconfluent graphs are outer-string graphs","Unit-interval graphs are strict confluent","Strict outerconfluent graphs have cop number two","Domino-free bipartite permutation graphs are strict outerconfluent"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000443,"raw_usage":{"total_tokens":2271,"prompt_tokens":1000,"completion_tokens":1271,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":616,"completion_tokens_details":{"reasoning_tokens":1192}},"tokens_in":616,"tokens_out":1271,"duration_ms":12130,"temperature":1.0,"reasoning_tokens":1192,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T13:17:31.867618+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Inspect the clique gadget in the proof of Theorem 3: for a clique of three vertices, the three incident arcs meet smoothly at a $\\Delta$-junction. Check whether this gadget can be converted into a sequence of binary merge/split junctions while preserving the property that each pair of vertices has exactly one smooth path. If no such conversion exists for some unit-interval graph (for instance, the smallest graph whose construction requires a $\\Delta$-junction), then the claimed inclusion of unit-interval graphs into SC would not be supported by the paper's construction, and one should search for a concrete unit-interval graph that admits no strict confluent drawing.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Defines strict confluent and strict outerconfluent drawings, including the binary merge/split junction model and the earlier SOC testing algorithm that this paper builds on."},{"cited_title":"Algorithmica 47(4), 465–479 (2007)","cited_arxiv_id":null,"evidence_quote":"Supplies Theorem 4, that bipartite-outerconfluent graphs equal bipartite permutation graphs, which Theorem 5 extends to the strict setting."},{"cited_title":"In: Graph Drawing (GD’05)","cited_arxiv_id":null,"evidence_quote":"Introduced $\\Delta$-confluent drawings and proved tree-like $\\Delta$-confluent graphs are distance-hereditary; Theorem 7 generalizes this to tree-like $\\Delta$-SOC graphs with a clique-width bound."},{"cited_title":"In: Algorithms and Computation (ISAAC’13)","cited_arxiv_id":null,"evidence_quote":"Established cop-number bounds for outer-string graphs and other intersection classes, providing the baseline against which Theorem 6's cop number two is measured."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the definitions of string graphs and outer-string graphs, the target superclasses in Theorems 1 and 2."},{"cited_title":"Theory Comput","cited_arxiv_id":null,"evidence_quote":"Supplies the clique-width framework and the algorithmic meta-theorems that make the bounded clique-width result in Theorem 7 significant."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Introduced confluent drawings and showed some graphs admit no confluent drawing; its obstruction examples are used in Appendix E for incomparability results."}],"review_version":1}