{"id":"3940c142-8010-4a40-b1e4-ecba023a0cf5","arxiv_id":"1908.08708","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Two planar graphs plus a tree always admit a simultaneous quasiplanar embedding, but simple instances with two quasiplanar graphs and a star, and fixed-drawing matching pairs, can fail.","lead":"Graph drawing researchers asked when several graphs sharing the same vertices can be drawn together without too many crossing edges. This paper introduces QuaSEFE, a relaxed simultaneous embedding rule where each graph avoids three mutually crossing edges, and proves which triples of graphs always fit and which cannot.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 7's proof is not self-contained: a proof/caption mismatch and a missing triple-crossing step leave the two-matchings counterexample unverified.","rationale":"The positive results appear sound: Theorem 2's two PEP applications are legitimate because the fixed subgraphs of the tree are forests, so Condition C.2 of Lemma 1 is vacuous, and any rotation scheme of a tree is planar, allowing the rotation-merging step described in the proof. Consequently Theorem 3 also goes through. The genuinely unsupported part is the negative matching result, which the abstract also advertises. The reader's weakest assumption pointed to the figure dependence of Theorem 7; I agree, and I add that the proof is internally inconsistent in a checkable way: the proof and the caption disagree over (v17,v19) versus (v18,v20), and the final quasiplanarity contradiction is missing the explicit pairwise-crossing triple. This is not a disagreement with the community's consensus; it is a correctness risk in the manuscript as submitted. Because the issue is localized to one theorem and may be fixable with a precise description of Fig. 1c and a fuller case analysis, the conditional verdict is appropriate rather than rejection. Thus I leave the reader's verdict unchanged.","tokens_in":7660,"tokens_out":28367,"duration_ms":290790,"concrete_test":"Ask the authors to provide explicit coordinates or a combinatorial cell decomposition for the drawing in Fig. 1c, then perform an arrangement-based search: enumerate all homotopy classes of curves from v17 to v19 (and separately from v18 to v20) that cross the ten fixed matching edges, and check whether every such curve creates a triangle in the crossing graph. In particular, verify whether the boundary edge (v1,v2) or (v3,v4) crosses both relevant dotted/dashed edges, since that is the only way crossing them together with the new edge forms a forbidden triple. If any route avoids such a triangle, Theorem 7's counterexample collapses.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The negative claim highlighted in the abstract, that a fixed quasiplanar drawing of one matching can make a second matching impossible to add, rests entirely on Theorem 7. As written, that proof is not verifiable. The geometric separation argument is delegated to Fig. 1c, and the text and caption disagree about which edge is forced to cross the dotted blue or dashed red edges: the proof says edge (v17,v19) crosses exactly one of (v1,v2) and (v3,v4) and then also crosses one dotted/dashed pair, whereas the caption says edge (v18,v20) crosses either all dotted blue or all dashed red edges. If the intended edge is (v18,v20), then the proof's claims about (v17,v19) do not establish the result; if the intended edge is (v17,v19), the role of (v18,v20) is unexplained and the caption is wrong. Moreover, the final step 'In both cases, (v5,v6) and (v7,v8) cannot be crossed, and thus (v17,v19) cannot be drawn so that Gamma2 is quasiplanar' is not a logical consequence of quasiplanarity as defined: quasiplanarity forbids three pairwise-crossing edges, and a new edge crossing several fixed edges is harmless unless those fixed edges already cross each other or the boundary edge in the appropriate way. The proof never identifies the specific triangle in the crossing graph that would be created. Because no coordinates or combinatorial description of Fig. 1c are supplied, a referee cannot check these claims. Since this negative result is one of the two headline contrasts with the planar SEFE setting, the paper's central claim is not fully supported as written.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper introduces QuaSEFE, a relaxation of simultaneous embedding with fixed edges in which every individual drawing is required to be quasiplanar, i.e., free of three pairwise crossing edges. The main positive results are that (i) any triple consisting of two planar graphs and a tree admits a QuaSEFE with the two planar graphs and the tree drawn planar (Theorem 2), which implies that a 1-planar graph together with a planar graph admits a QuaSEFE (Theorem 3); (ii) further sufficient conditions for triples of planar graphs depending on the structure of their common subgraphs (Theorems 1, 4, 5 and Corollaries 1-4); and (iii) two negative results: a non-simple QuaSEFE obstruction involving two quasiplanar graphs and a star (Theorem 6), and an example showing that a fixed quasiplanar drawing of one matching cannot always be extended by a second matching (Theorem 7).","tokens_in":8025,"tokens_out":24889,"duration_ms":234198,"significance":"If the proofs are made fully rigorous, the paper is a solid contribution: it opens a new direction in simultaneous graph drawing by combining SEFE with beyond-planar readability, it gives clean sufficient conditions using the PEP characterization and known edge bounds, and it provides a notable contrast with the planar SEFE setting. Theorems 1, 4, and 5 are straightforward and convincing, and the application to 1-planar graphs in Theorem 3 is elegant. The main risk is the negative result in Theorem 7, which is one of the two headline contrasts with planar SEFE and is currently not verifiable from the text because the proof is incomplete and the caption of Fig. 1c disagrees with the proof. The paper deserves publication after a major revision that supplies the missing definitions and case analysis.","major_comments":[{"comment":"The definition of the matching M2 is incomplete. The proof says \"let E2 contain the edges (v17,v19) and (v18,v20)\", but M2 is supposed to be a matching on V, and the quasiplanarity argument only makes sense if E2 also contains the eight common matching edges (v_{2i-1},v_{2i}) for i=1,...,8, which are then fixed by Gamma1. If E2 consists only of the two new edges, then Gamma2 is trivially quasiplanar and no contradiction arises. Please define E2 explicitly, for example as (E1 \\ {(v17,v18),(v19,v20)}) union {(v17,v19),(v18,v20)}.","section":"Section 3, Theorem 7"},{"comment":"There is a mismatch between the proof and the caption of Fig. 1c. The proof argues about edge (v17,v19), whereas the caption states that edge (v18,v20) crosses either all dotted blue or all dashed red edges. If the intended edge is (v18,v20), then the proof's statements about (v17,v19) do not establish the claimed obstruction; if the intended edge is (v17,v19), the role of (v18,v20) is unexplained. This discrepancy must be corrected before the proof can be evaluated.","section":"Section 3, Theorem 7"},{"comment":"The final contradiction is not a logical consequence of quasiplanarity as stated. After establishing that (v17,v19) crosses one of (v1,v2) or (v3,v4) and then one of the two colored pairs, the proof claims that \"(v5,v6) and (v7,v8) cannot be crossed\", but it never identifies the three pairwise crossing edges in Gamma2 that would arise. Since quasiplanarity forbids exactly those triples, one must explicitly show that crossing (v5,v6) or (v7,v8) creates a triple with the already-crossed boundary edge and one of the dotted or dashed edges. The proof also does not justify the assertion that (v17,v19) crosses \"exactly one\" of the two boundary edges rather than both; while this may follow from quasiplanarity and a parity argument, it needs to be stated. Please provide a complete case analysis or a precise combinatorial/geometric description of Fig. 1c from which these route claims can be checked.","section":"Section 3, Theorem 7"}],"minor_comments":[{"comment":"The PEP application in Theorem 2 is terse. Please spell out that the second PEP call for G3 has fixed subgraph (T2 cap G3) \\ G1, while the edges of G1 cap G3 are already drawn in Gamma1, so that G3 is decomposed into the two planar sets G3 \\ G1 and G1 cap G3. This would make the crossing partition in the last sentence explicit.","section":"Section 2, Theorem 2"},{"comment":"In the last sentence of the proof of Theorem 2, \"crossings edges of the same graph belong to G3\\G1 and G3 cap G1\" should read \"crossing edges of the same graph belong ...\".","section":"Section 2, Theorem 2"},{"comment":"In Theorem 4, the proof should state explicitly that the common graph H is drawn once and then extended to G1, G2, and G3 using the assumed common embedding, so that the three drawings agree on H; otherwise the phrase \"we draw ... with embedding Gi\" does not by itself guarantee that shared edges are drawn identically.","section":"Section 2, Theorem 4"},{"comment":"The proof of Theorem 6 relies entirely on the existence of the simple quasiplanar drawing of Q1 shown in Fig. 1b. Since the figure is not described in the text, please either include the construction from Brandenburg's K10 drawing explicitly or provide a reference/coordinates so that the drawing can be verified.","section":"Section 3, Theorem 6"},{"comment":"The definition of QuaSEFE does not state whether drawings are assumed to be simple (no adjacent crossings, at most one crossing per edge pair) in general. The paper later defines simple specifically for Theorem 6, but Theorem 7 may depend on standard topological-drawing conventions; please state the convention used throughout.","section":"Section 1, Definition 1"}],"recommendation":"major_revision","confidential_remarks":"The positive results of the paper appear sound and interesting. The negative result in Theorem 7 is a headline contribution but is currently not verifiable because of the incomplete definition of M2, the proof/caption mismatch, and the missing triple-crossing case analysis. If these issues can be repaired with a precise description of Fig. 1c, the paper would be suitable for publication; otherwise the abstract's contrast with planar SEFE would be unsupported."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Quick take: the QuaSEFE model is a natural relaxation of SEFE, and the positive results are worth having. The paper proves that any triple of two planar graphs plus a tree admits a QuaSEFE with planar drawings of both the planar graph and the tree, which gives the 1-planar-plus-planar corollary. Those proofs are assembled from PEP and planar embedding tools, not deep, but they are new and constructive. The sunflower generalization and Theorem 6's edge-count argument also work. This is a real contribution.\n\nThe soft spot is Theorem 7, the matching counterexample. The stress-test note is right: the proof as written is not verifiable. The proof text and figure caption disagree about whether (v17,v19) or (v18,v20) is the forcing edge. The final inference, that (v17,v19) cannot be drawn quasiplanarly because it crosses certain fixed edges, never names the triple of pairwise-crossing edges that would violate quasiplanarity. A fixed edge can cross a new edge several times without creating three pairwise-crossing edges. So a referee cannot check the claim from the text. If the construction in Fig 1c is realizable, the theorem may be true, but the paper needs a coordinate or combinatorial description and a proper crossing-graph argument.\n\nTheorem 2 has a smaller issue. The PEP step is compressed: it fixes T2∩G1 and then merges rotations from G*3, but the merge step is only sketched. The reader suggests running PEP on T2∩G3 rather than on (T2∩G3)\\G1; either way, the current text is terse enough that a referee should ask for expansion. This is minor, not fatal.\n\nBottom line: the paper deserves a serious referee. The positive results stand, and the matching counterexample is a plausible, interesting claim that needs a rigorous write-up. I'd send it to review with a clear request to fix Theorem 7; if that cannot be fixed, the abstract should drop or soften the matching claim.","headline":"A genuinely useful positive result for QuaSEFE, but the headline matching counterexample is not verifiable as written and needs a serious rewrite.","tokens_in":8570,"tokens_out":2588,"would_cite":true,"duration_ms":26151,"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":"Any two planar graphs and a tree on the same vertices admit a simultaneous quasiplanar drawing, and any 1-planar graph pairs with any planar graph in the same way.","keywords":["QuaSEFE","simultaneous embedding with fixed edges","quasiplanar graphs","beyond planarity","1-planar graphs","partially embedded planarity","graph drawing","SEFE"],"falsifier":"Redraw the ten-edge matching of Fig. 1c and try to route the edge $(v_{17},v_{19})$ from inside the lens to $v_{19}$ so that it crosses at most two of the existing matching edges and avoids $(v_5,v_6)$ and $(v_7,v_8)$; any such curve disproves the claimed impossibility, while exhaustive failure of all routes supports it.","tokens_in":7501,"feed_emoji":"📐","tokens_out":8532,"duration_ms":76479,"temperature":0.7,"pith_summary":"This paper introduces the QuaSEFE problem: given several graphs on the same vertex set, draw each one so that vertices coincide and shared edges are drawn identically, but allow crossings as long as no three edges of the same graph cross one another, which is a quasiplanar drawing. The main positive result is that any triple consisting of two planar graphs and a tree admits such a QuaSEFE, and the construction can keep one planar graph and the tree planar while the other planar graph is only required to be quasiplanar. From this, the paper derives that any pair formed by a 1-planar graph and a planar graph admits a QuaSEFE, a statement with no analogue known in the planar-only SEFE setting. On the negative side, it exhibits a triple of two quasiplanar graphs and a star with no simple QuaSEFE, and it shows that a fixed quasiplanar drawing of one matching cannot always be extended to a second matching, in contrast to the planar SEFE setting. The paper thereby establishes that relaxing planarity to quasiplanarity enlarges the family of simultaneously embeddable graphs and that some limitations persist in restricted settings.","feed_headline":"Two planar graphs plus a tree always share a quasiplanar drawing","feed_subtitle":"Relaxing no-crossing to no-three-crossing turns a hard embedding problem into a yes.","key_machinery":"The load-bearing mechanism for the positive results is the partially embedded planarity (PEP) criterion: a planar embedding of a graph extends to a planar embedding of a larger graph exactly when the rotation scheme around each vertex is preserved and every cycle separates the same vertices inside and outside as before. Because a tree has no cycles, the cycle condition is automatic, so the paper can fix a planar embedding of one planar graph, add the tree edges compatibly, and then add the remaining edges of the other planar graph while keeping each graph's edge set split into two planarly drawn parts that only cross each other. The negative results rest on two different mechanisms: the extremal bound of $6.5n-20$ edges for simple quasiplanar graphs on $n$ vertices, which lets a 52-edge union of two quasiplanar graphs on 11 vertices force a crossing violation involving edges of the shared star; and a lens-shaped drawing of a ten-edge matching in which every route for a new edge must cross one of two triples of existing edges, leaving the remaining edges uncrossable.","core_discovery":"The central claim is that the simultaneous embedding problem becomes substantially more tractable when the per-graph readability requirement is relaxed from planarity to quasiplanarity. Formally, Theorem 2 states that for any two planar graphs $G_1$ and $G_3$ and any tree $T_2$ sharing a vertex set $V$, the triple $\\langle G_1,T_2,G_3\\rangle$ admits a QuaSEFE in which $G_1$ and $T_2$ are drawn planar; Theorem 3 then shows that any 1-planar graph and planar graph on the same vertices admit a QuaSEFE, because a 1-planar graph splits into a planar graph plus a forest that can be augmented to a tree. Positive results also cover triples of planar graphs whose pairwise or common subgraphs have simple structure, including the sunflower setting where every edge is either private to one graph or common to all graphs, which works for any number of planar graphs even though the planar SEFE problem is NP-complete there. The negative results prove limits: a simple QuaSEFE is not guaranteed for two quasiplanar graphs and a star, and two matchings can fail to admit a QuaSEFE when one matching's quasiplanar drawing is fixed in advance.","pith_inferences":["Because the positive proof only exploits that a tree has no cycles, the same PEP-based construction may extend to triples in which one graph is any forest or, more generally, any graph whose cycles can be accommodated in the cycle-separation condition.","The two-matchings counterexample suggests a quasiplanar version of the partially embedded planarity problem is not always solvable, so its computational complexity is a natural target; it may be NP-complete even for matchings.","Since the 1-planar result comes from decomposing the 1-planar graph into a planar graph plus a forest, analogous decompositions of $k$-planar graphs could yield QuaSEFE results for $k$-planar and planar pairs for larger $k$.","The sunflower positive result indicates that, in the quasiplanar setting, the difficulty is not how complex each graph is but which edges are shared; this may transfer to other beyond-planar classes such as $k$-planar or RAC graphs."],"forward_implications":["Any triple of two planar graphs and a tree admits a QuaSEFE, constructible in linear time, with one planar graph and the tree drawn planar.","Any pair of a 1-planar graph and a planar graph admits a QuaSEFE, giving the first simultaneous embedding result for a beyond-planar graph class in this fixed-edge setting.","In the sunflower setting, any number of planar graphs admits a QuaSEFE, even though the analogous planar SEFE problem is NP-complete there.","Simple QuaSEFEs are not guaranteed: there is a triple of two quasiplanar graphs plus a star that has no simple QuaSEFE.","A fixed quasiplanar drawing of one matching cannot always be extended to a second matching, so the quasiplanar analogue of partially embedded planarity fails already for matchings."],"supporting_citations":[{"why":"Supplies the partially embedded planarity criterion (Lemma 1) that the proof of Theorem 2 uses to extend the tree and the second planar graph.","marker":"[5]"},{"why":"Establishes that every pair of a planar graph and a tree admits a SEFE, the basis for Corollary 1 and the contrast used in Theorem 7.","marker":"[19]"},{"why":"Provides the algorithm for drawing the remaining edges of a planar graph at fixed vertex locations, used in Theorem 1.","marker":"[23]"},{"why":"Gives the decomposition of 1-planar graphs into a planar graph plus a forest, which Theorem 3 augments to a tree.","marker":"[1]"},{"why":"Supplies the $6.5n-20$ edge bound for simple quasiplanar graphs that drives the counting argument in Theorem 6.","marker":"[2]"},{"why":"Provides the simple quasiplanar drawing of $K_{10}$ from which the quasiplanar graphs $Q_1$ and $Q_2$ in Theorem 6 are built.","marker":"[11]"}],"fun_headline_variants":["Two planar graphs and any tree always admit a quasiplanar embedding","Quasiplanar shared drawing always exists for two planars and a tree","For two planar graphs and any tree, QuaSEFE is guaranteed"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The two-matchings counterexample rests on the specific geometry of the ten-edge matching in Fig. 1c: vertex $v_{17}$ lies inside the lens formed by two crossing edges, and every curve from $v_{17}$ to $v_{19}$ must cross either the three dashed edges or the three dotted edges; if that arrangement is not realizable exactly as asserted, that counterexample collapses.","fun_headline_variants_meta":{"raw":{"variants":["Two planar graphs and any tree always admit a quasiplanar embedding","Quasiplanar shared drawing always exists for two planars and a tree","For two planar graphs and any tree, QuaSEFE is guaranteed"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001015,"raw_usage":{"total_tokens":4302,"prompt_tokens":975,"completion_tokens":3327,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":591,"completion_tokens_details":{"reasoning_tokens":3265}},"tokens_in":591,"tokens_out":3327,"duration_ms":26939,"temperature":1.0,"reasoning_tokens":3265,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T11:33:04.995857+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Redraw the ten-edge matching of Fig. 1c and try to route the edge $(v_{17},v_{19})$ from inside the lens to $v_{19}$ so that it crosses at most two of the existing matching edges and avoids $(v_5,v_6)$ and $(v_7,v_8)$; any such curve disproves the claimed impossibility, while exhaustive failure of all routes supports it.","supporting_citations":[{"cited_title":"Discrete Applied Mathematics 175, 104–108 (2014)","cited_arxiv_id":null,"evidence_quote":"Gives the decomposition of 1-planar graphs into a planar graph plus a forest, which Theorem 3 augments to a tree."},{"cited_title":"In: Hu, Y., N¨ ollenburg, M","cited_arxiv_id":null,"evidence_quote":"Provides the simple quasiplanar drawing of $K_{10}$ from which the quasiplanar graphs $Q_1$ and $Q_2$ in Theorem 6 are built."}],"review_version":1}