REVIEW 3 major objections 5 minor 25 references
The QuaSEFE Problem
T0 review · 3 major / 5 minor · reviewed 2026-08-14 · deepseek-v4-flash
Pith's one-line read 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.
desk verdict A genuinely useful positive result for QuaSEFE, but the headline matching counterexample is not verifiable as written and needs a serious rewrite. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
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.
What would settle it
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.
Extended reading notes
Core claim
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.
Load-bearing premise
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.
Editorial extensions
If this is right
- 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.
Reading between the lines
- 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.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
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).
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 (3)
- [Section 3, Theorem 7] 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 3, Theorem 7] 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 3, Theorem 7] 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.
minor comments (5)
- [Section 2, Theorem 2] 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 2, Theorem 2] 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 2, Theorem 4] 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 3, Theorem 6] 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 1, Definition 1] 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.
Circularity Check
No significant circularity: the proofs reduce to external established theorems, not to their own conclusions.
full rationale
The derivation chain is self-contained relative to published external results and does not reduce to its own inputs. Theorem 1 combines a SEFE of two graphs with the Pach-Wenger embedding algorithm for drawing a planar graph at fixed vertex locations. Corollary 1 uses Frati's result that every planar graph and tree admit a SEFE. Theorem 2 uses the PEP characterization stated as Lemma 1 from [5]; although some authors of the present paper are among the authors of [5], that characterization is an independent published theorem with stated conditions (C.1 and C.2) that do not mention QuaSEFE or the target statement. Theorem 3 uses Ackerman's decomposition of 1-planar graphs into a planar graph and a forest, an external combinatorial fact. Theorem 5 draws each graph independently, and Theorem 6 uses the Ackerman-Tardos edge bound for simple quasiplanar graphs. No fitted parameter is renamed as a prediction, no definition is circular, and no load-bearing claim is justified solely by a self-citation. The proof of Theorem 7 has a verifiability concern: the text and Fig. 1c caption disagree about whether edge (v17,v19) or (v18,v20) is the one forced to cross the dotted or dashed edges, and the last inference about quasiplanarity is not fully spelled out. That is a correctness or exposition gap, not circularity, because the alleged counterexample is not obtained by assuming what it proves. Overall, the paper's central results rest on independent external theorems and are not circular.
Assumptions & free parameters
assumptions (5)
- standard math PEP characterization (Lemma 1 from [5]): a planar embedding G of G is a solution for PEP instance (G,H,H) iff conditions C.1 and C.2 hold.
- standard math Every 1-planar graph is the union of a planar graph and a forest [1].
- standard math Maximum number of edges in a simple quasiplanar graph with n vertices is 6.5n - 20 [2].
- standard math Every pair consisting of a planar graph and a tree admits a SEFE [19].
- standard math Every planar graph can be embedded with straight-line edges at any prescribed set of vertex locations in general position [23].
Cite this review
Pith. "Pith review of The QuaSEFE Problem." pith.science (2026). https://pith.science/paper/AYWIBBAB
@misc{pith2026190808708,
author = {Pith},
title = {Pith review of: The QuaSEFE Problem},
year = {2026},
howpublished = {\url{https://pith.science/paper/AYWIBBAB}},
note = {Machine review of arXiv:1908.08708}
}
read the original abstract
We initiate the study of Simultaneous Graph Embedding with Fixed Edges in the beyond planarity framework. In the QuaSEFE problem, we allow edge crossings, as long as each graph individually is drawn quasiplanar, that is, no three edges pairwise cross. We show that a triple consisting of two planar graphs and a tree admit a QuaSEFE. This result also implies that a pair consisting of a 1-planar graph and a planar graph admits a QuaSEFE. We show several other positive results for triples of planar graphs, in which certain structural properties for their common subgraphs are fulfilled. For the case in which simplicity is also required, we give a triple consisting of two quasiplanar graphs and a star that does not admit a QuaSEFE. Moreover, in contrast to the planar SEFE problem, we show that it is not always possible to obtain a QuaSEFE for two matchings if the quasiplanar drawing of one matching is fixed.
Figures
Reference graph
Works this paper leans on
-
[1]
Discrete Applied Mathematics 175, 104–108 (2014)
Ackerman, E.: A note on 1-planar graphs. Discrete Applied Mathematics 175, 104–108 (2014). https://doi.org/10.1016/j.dam.2014.05.025
-
[2]
Journal of Combinatorial Theory, Series A 114(3), 563 – 571 (2007)
Ackerman, E., Tardos, G.: On the maximum number of edges in quasi-planar graphs. Journal of Combinatorial Theory, Series A 114(3), 563 – 571 (2007). https://doi.org/10.1016/j.jcta.2006.08.002
-
[3]
Combinatorica 17(1), 1–9 (1997)
Agarwal, P.K., Aronov, B., Pach, J., Pollack, R., Sharir, M.: Quasi-planar graphs have a linear number of edges. Combinatorica 17(1), 1–9 (1997). https://doi.org/10.1007/BF01196127
-
[4]
Angelini, P., Da Lozzo, G., Neuwirth, D.: Advancements on SEFE and par- titioned book embedding problems. Theor. Comput. Sci. 575, 71–89 (2015). https://doi.org/10.1016/j.tcs.2014.11.016
-
[5]
Angelini, P., Di Battista, G., Frati, F., Jel´ ınek, V., Kratochv´ ıl, J., Patrignani, M., Rutter, I.: Testing planarity of partially embedded graphs. ACM Trans. Algorithms 11(4), 32:1–32:42 (2015). https://doi.org/10.1145/2629341
doi:10.1145/2629341 2015
-
[6]
Angelini, P., Geyer, M., Kaufmann, M., Neuwirth, D.: On a tree and a path with no geometric simultaneous embedding. J. Graph Algorithms Appl. 16(1), 37–83 (2012)
work page 2012
-
[7]
Argyriou, E.N., Bekos, M.A., Kaufmann, M., Symvonis, A.: Geometric RAC si- multaneous drawings of graphs. J. Graph Algorithms Appl. 17(1), 11–34 (2013). https://doi.org/10.7155/jgaa.00282
-
[8]
Bekos, M.A., van Dijk, T.C., Kindermann, P., Wolff, A.: Simultaneous drawing of planar graphs with right-angle crossings and few bends. J. Graph Algorithms Appl. 20(1), 133–158 (2016). https://doi.org/10.7155/jgaa.00388
Show all 25 references
-
[9]
In: Tamassia, R
Bl¨ asius, T., Kobourov, S.G., Rutter, I.: Simultaneous embedding of planar graphs. In: Tamassia, R. (ed.) Handbook on Graph Drawing and Visualization., pp. 349–
-
[10]
ACM Trans
Bl¨ asius, T., Rutter, I.: Simultaneous PQ-ordering with applications to con- strained embedding problems. ACM Trans. Algorithms 12(2), 16:1–16:46 (2016). https://doi.org/10.1145/2738054
2016 doi
-
[11]
In: Hu, Y., N¨ ollenburg, M
Brandenburg, F.J.: A simple quasi-planar drawing of K10. In: Hu, Y., N¨ ollenburg, M. (eds.) Graph Drawing. LNCS, vol. 9801, pp. 603–604. Springer (2016)
2016
-
[12]
Com- put
Braß, P., Cenek, E., Duncan, C.A., Efrat, A., Erten, C., Ismailescu, D., Kobourov, S.G., Lubiw, A., Mitchell, J.S.B.: On simultaneous planar graph embeddings. Com- put. Geom. 36(2), 117–130 (2007). https://doi.org/10.1016/j.comgeo.2006.05.006
2007 doi
-
[13]
Di Giacomo, E., Didimo, W., Liotta, G., Meijer, H., Wismath, S.K.: Planar and quasi-planar simultaneous geometric embedding. Comput. J. 58(11), 3126–3140 (2015). https://doi.org/10.1093/comjnl/bxv048
2015 doi
-
[14]
Didimo, W., Kaufmann, M., Liotta, G., Okamoto, Y., Spillner, A.: Vertex angle and crossing angle resolution of leveled tree drawings. Inf. Process. Lett. 112(16), 630–635 (2012). https://doi.org/10.1016/j.ipl.2012.05.006
2012 doi
-
[15]
ACM Comput
Didimo, W., Liotta, G., Montecchiani, F.: A survey on graph draw- ing beyond planarity. ACM Comput. Surv. 52(1), 4:1–4:37 (2019). https://doi.org/10.1145/3301281
2019 doi
-
[16]
In: Hong, S., Nishizeki, T., Quan, W
Estrella-Balderrama, A., Gassner, E., J¨ unger, M., Percan, M., Schaefer, M., Schulz, M.: Simultaneous geometric graph embeddings. In: Hong, S., Nishizeki, T., Quan, W. (eds.) 15th International Symposium on Graph Drawing, GD 2007. LNCS, vol. 4875, pp. 280–290. Springer (2007)...
2007 doi
-
[17]
Evans, W.S., Liotta, G., Montecchiani, F.: Simultaneous visibility representations of plane st-graphs using L-shapes. Theor. Comput. Sci. 645, 100–111 (2016). https://doi.org/10.1016/j.tcs.2016.06.045
2016 doi
-
[18]
SIDMA 27(1), 550–561 (2013)
Fox, J., Pach, J., Suk, A.: The number of edges in k-quasi-planar graphs. SIDMA 27(1), 550–561 (2013). https://doi.org/10.1137/110858586
2013 doi
-
[19]
In: Kaufmann, M., Wagner, D
Frati, F.: Embedding graphs simultaneously with fixed edges. In: Kaufmann, M., Wagner, D. (eds.) Graph Drawing, 14th International Symposium, GD 2006. LNCS, vol. 4372, pp. 108–113. Springer (2006). https://doi.org/10.1007/978-3-540- 70904-6 12
2006 doi
-
[20]
Grilli, L.: On the NP-hardness of GRacSim drawing and k- SEFE problems. J. Graph Algorithms Appl. 22(1), 101–116 (2018). https://doi.org/10.7155/jgaa.00456
2018 doi
-
[21]
Haeupler, B., Jampani, K.R., Lubiw, A.: Testing simultaneous planarity when the common graph is 2-connected. J. Graph Algorithms Appl. 17(3), 147–171 (2013). https://doi.org/10.7155/jgaa.00289
2013 doi
-
[22]
Hopcroft, J.E., Tarjan, R.E.: Efficient planarity testing. J. ACM 21(4), 549–568 (1974). https://doi.org/10.1145/321850.321852
1974
-
[23]
Graphs and Combinatorics 17(4), 717–728 (2001)
Pach, J., Wenger, R.: Embedding planar graphs at fixed vertex locations. Graphs and Combinatorics 17(4), 717–728 (2001). https://doi.org/10.1007/PL00007258
2001 doi
-
[24]
Schaefer, M.: Toward a theory of planarity: Hanani-tutte and pla- narity variants. J. Graph Algorithms Appl. 17(4), 367–440 (2013). https://doi.org/10.7155/jgaa.00298
2013 doi
-
[381]
Chapman and Hall/CRC (2013)
2013
Reviewed August 14, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.