Geometry and Generation of a New Graph Planarity Game

Andr\'e van Renssen; Marc van Kreveld; Rutger Kraaijer; Wouter Meulemans

REVIEW 2 major objections 4 minor 20 references

Geometry and Generation of a New Graph Planarity Game

T0 review · 2 major / 4 minor · reviewed 2026-08-14 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Deciding whether a sequence of vertex swaps can untangle a drawing is NP-complete, and for trees deciding whether k swaps suffice is NP-complete as well.

desk verdict Worth reading for the clean lower bound, the Cabello-based NP-completeness reduction, and the order-type equivalence theorem, but the tree NP-hardness proof has an unproved clause-gadget lower bound that is load-bearing. read the letter →

arxiv 1908.01426 v1 pith:JVKAAZDG submitted 2019-08-05 cs.CG

Rutger Kraaijer , Marc van Kreveld , Wouter Meulemans , André van Renssen This is my paper · ORCID

classification cs.CG MSC 05C1068Q1768R10

keywords SwapPlanaritygraphdrawingNP-completenessplanaruntanglingpuzzlegenerationordertype1-in-3-SATDelaunaytriangulation

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper introduces Swap Planarity, a puzzle in which each move swaps the locations of two vertices joined by an edge, and asks when swaps can turn a tangled drawing into a plane drawing. It shows that solving the puzzle is computationally hard: deciding whether any swap sequence reaches a plane drawing is NP-complete, and for trees, where a plane drawing always exists, deciding whether $k$ swaps suffice is also NP-complete. The paper also proves that a solvable instance never needs more than $O(n^2)$ swaps, that some one-crossing instances require $\Omega(n^2)$ swaps, and that two connected non-star drawings are equivalent exactly when their graphs are isomorphic and their point sets share the same order type. It then describes a five-step generator that produces visually clear, varied puzzle instances and reports experiments on the trade-off between visual clarity and diversity.

What carries the argument

The argument is carried by a gadget reduction from positive planar 1-in-3-SAT. Variable gadgets are long paths whose crossings are resolved by swapping either all even or all odd vertical edges, encoding false or true; split gadgets pass that value to a clause; and each clause gadget is designed so that exactly one true variable lets all crossings be removed in five swaps while zero or multiple true variables force at least six. For the upper bound, the paper uses a path-bubble argument in which swapping along a path between a misplaced vertex and its target position moves one token into place in $O(n)$ swaps, yielding $O(n^2)$ overall. A separate equivalence result identifies a drawing with another precisely when the underlying graphs are isomorphic and the point sets share the same order type, enabling an $O(n^3)$ equivalence test.

What would settle it

Enumerate all swap sequences of length at most five on the clause gadget with zero, two, or three true incoming variables; if any such sequence produces a plane drawing, the Theorem 4 reduction fails to separate satisfiable from unsatisfiable instances.

Watch

Extended reading notes

Core claim

The central discovery is that swap-based untangling is NP-complete even for trees: given an embedded tree and an integer $k$, asking whether $k$ swaps of edge endpoints can produce a plane drawing is NP-complete (Theorem 4). The proof reduces positive planar 1-in-3-SAT to the swap-count problem, wiring variable, split, and clause gadgets so that each satisfied clause can be untangled in five swaps while unsatisfied clauses require more. In addition, the paper proves that deciding solvability for general graphs is NP-complete (Theorem 3), that any solvable instance can be planarized with $O(n^2)$ swaps while some cycles with a single crossing require $\Omega(n^2)$ swaps, and that two connected non-star drawings are swap-equivalent exactly when their graphs are isomorphic and their point sets have the same order type.

Load-bearing premise

The load-bearing premise is the claim that no clever alternative sequence of swaps can untangle the small arrangement that encodes a logical clause in fewer than six moves when the clause is unsatisfied; this is argued informally rather than proved exhaustively, and the NP-completeness reduction depends on it.

Editorial extensions

If this is right

Every solvable instance can be solved in $O(n^2)$ swaps, so the puzzle never demands unboundedly long solution sequences.
Some instances with only one edge crossing require $\Omega(n^2)$ swaps, so a visually simple puzzle can hide a large search.
Because the general decision problem is NP-complete, no polynomial-time algorithm solves arbitrary instances unless P equals NP.
Because the tree version with a swap budget is NP-complete, optimal play is hard to automate even for the simplest graph class.
Swap-equivalence of two connected non-star drawings can be tested in $O(n^3)$ time, giving a concrete notion of instance diversity.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

A corollary the paper does not spell out is that exact optimal play is out of reach for large instances, so practical generators must fall back on brute force for small swap counts or heuristics, the trade-off the experimental section measures.
The equivalence theorem suggests a natural distance measure for puzzle instances based on the size of the order-type matching that also preserves graph isomorphism, which could be used to diversify generated puzzles beyond the geometric indicators reported.
If the clause-gadget lower bound is correct, the same gadget family could probably be adapted to prove NP-completeness for other swap-restricted drawing variants, such as the rotation or stretch variants the paper lists but does not analyze.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

The paper is a genuinely nice piece of puzzle-geometry work: it defines Swap Planarity, proves a clean Omega(n^2) lower bound, gives a straightforward NP-completeness reduction from fixed-point-set planar embedding, proves an O(n^2) upper bound via known token-swapping results, and characterizes puzzle equivalence in terms of order types. The generation experiments are described well enough to reproduce, and the writing is clear and honest about what is known versus what is new.

What stands out as solid: Lemma 1 is rigorous and elegant; Theorem 3 follows correctly from Cabello's theorem; Section 6's equivalence result is properly proved and genuinely useful; the citation pattern is fair, crediting Yamanaka et al. and Mulzer-Rote where due. There are no fitted parameters, and the paper does not assume its own conclusions.

The soft spot is Theorem 4. The reduction's threshold is five swaps per clause, so the entire if-and-only-if depends on the claim that an unsatisfied clause requires at least six swaps. The only support for that claim is the paragraph beginning 'It remains to argue that there is no globally different set of swaps.' That paragraph is an informal sketch, not a proof. It asserts that each crossing must be paid for by a dedicated nearby swap and that aligning the triangle layers is the only cheap way, but it does not rule out a single swap that moves an endpoint and simultaneously clears crossings in several layers, nor does it exclude swaps shared between the clause gadget and adjacent split or variable gadgets. This is load-bearing, not a minor gap. The rest of Theorem 4—the gadget constructions and the correspondence between truth assignments and swap counts—is plausible, but the lower bound is the hard part and it is currently asserted rather than demonstrated.

Minor concerns: no code or data is shipped for the generation experiments, and the claim that 'no puzzle instance cannot be generated' is stronger than what the experiments actually show. These are small; the main issue is the proof gap in Theorem 4.

Who is this for? Graph drawing researchers, puzzle complexity people, and anyone designing abstract geometric games. The lower bound, the general NP-completeness reduction, and the equivalence theorem stand on their own regardless of Theorem 4. The paper deserves a serious referee. I would send it out, but I would tell the authors that Theorem 4's key lower-bound argument needs a complete case analysis or a formalized proof before the result can be accepted as certified.

Referee Report

2 major / 4 minor

Summary. The paper introduces Swap Planarity, a puzzle in which a move exchanges the positions of the two endpoints of an edge, and the goal is to reach a crossing-free straight-line drawing. It proves that some n-vertex instances require Ω(n²) swaps (Lemma 1), that any solvable instance can be solved in O(n²) swaps (Lemma 2), that deciding solvability is NP-complete for general graphs (Theorem 3), and that deciding whether a tree can be solved in at most k swaps is NP-complete (Theorem 4). The paper then proposes a five-step generator for puzzle instances with guarantees on visual separation, diversity, and absence of recognizable structure, reports experiments on point generation and convex-hull statistics, and characterizes swap-equivalence of two instances in terms of simultaneous graph isomorphism and order-type equivalence (Section 6).

Significance. If the proofs are completed, the paper's main algorithmic contribution is the NP-completeness of bounded-swap planarity for trees, which is a genuinely nontrivial contrast with the polynomial-time solvability of ordinary planarity for trees; the Ω(n²)/O(n²) bounds and the order-type characterization are also useful. The generation process and experiments are a practical contribution, and the paper is clearly written with reproducible constructions. Its central complexity claims are, however, conditional on the clause-gadget lower bound in Theorem 4, and the equivalence theorem needs a small domain correction.

major comments (2)

[§3, Theorem 4 (clause-gadget lower bound)] The NP-hardness reduction for trees is not yet proven, because the lower bound for unsatisfied clauses is only sketched in the paragraph beginning 'It remains to argue that there is no globally different set of swaps...'. The text asserts that each crossing must be paid for by a dedicated nearby swap, that aligning the three triangle layers is the only way to clear the central crossings in few moves, and that swapping a triangle-layer vertex out costs at least two swaps per layer, but none of these assertions is derived. In particular, the argument does not rule out a swap that simultaneously resolves crossings in several layers, nor swaps shared between the clause gadget and the adjacent split or variable gadgets. Since the reduction's threshold is five swaps per clause, any unsatisfied assignment admitting a five-swap solution would invalidate the if-and-only-if. A complete case analysis (or a machine-checked enumeration of the gadget's swap sequences) is needed before Theorem 4 can be considered proved.
[§6, Lemma 8 and Theorem 9] The claim that every connected non-star graph has two edges with four distinct vertices is false: the triangle K3 is connected and not a star, but its edges pairwise share vertices. For K3, any two straight-line drawings on three non-collinear points are swap-equivalent under every vertex matching, because all three edges are mutually adjacent and no two edges can cross; however, the two point sets can have different order types (opposite orientations). This contradicts Theorem 9 as stated. The theorem needs an explicit exception for triangle graphs, or a hypothesis that the graph has at least four vertices (or matching number at least two).

minor comments (4)

[§3, Theorem 4] The total k for the reduction is not defined explicitly; the proof should state a concrete formula, for example k = B + 5m for a baseline B depending only on the variable and split structure, and should prove that B is independent of the truth assignment.
[§3, Theorem 4] The step 'To construct a tree, we remove the middle edges from some basic constructions' should specify that the removed edges are chosen on cycles so that the graph remains connected; removing a bridge would produce a forest rather than a tree.
[§3, Lemma 2 and Theorem 3] Lemma 2 is stated only for reaching a plane drawing, but Theorem 3 and Lemma 8 invoke the stronger fact that any target bijection can be realized in a connected graph; the lemma's proof actually establishes this stronger statement, so it should be stated explicitly.
[References] Reference [19] misspells 'Theoretical Computer Science' as 'Theoretical Compututer Science'.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity found: NP-completeness results rest on external reductions, and the only weakness is an informal lower-bound argument, which is a proof gap rather than a circular step.

full rationale

The paper's central results (Theorem 3 and Theorem 4) are reductions from external NP-complete problems: Cabello's fixed point-set planar embeddability for general graphs, and Mulzer and Rote's positive planar 1-in-3-SAT for trees. Lemma 2's O(n^2) upper bound is proved in the text and attributed to prior token-swapping work [20]; it is used as a subroutine, not as the target claim. Lemma 1 is self-contained via an inversion argument. The generation section's delta-general position idea is new, and the sole author self-citation [18] is for a geometric separation criterion that is not load-bearing for the complexity claims. The one passage that deserves scrutiny is in Theorem 4's proof: 'It remains to argue that there is no globally different set of swaps that makes the graph plane with fewer operations.' That paragraph is an informal sketch, not a complete case analysis; if the lower bound fails, the tree NP-completeness proof would be incomplete. However, this is a missing proof case, not circularity: the conclusion is not assumed in the premises, no fitted parameter is relabeled as a prediction, and no equation is equal to another by construction. Hence the circularity score is 0.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

The paper's complexity results are obtained by reductions from established NP-complete problems rather than by postulating new computational primitives. The generation section introduces the parameter delta for visual separation, but delta is a user-chosen design parameter, not a fitted quantity. No free parameters or invented entities are used to derive the main claims.

assumptions (4)

domain assumption Point-set embeddability of a graph onto a given point set is NP-complete (Cabello, 2006).
Used as the starting problem for the reduction proving NP-completeness of deciding if a Swap Planarity instance can be made planar (Theorem 3).
domain assumption Positive planar 1-in-3-SAT is NP-complete (Mulzer and Rote, 2008).
Source problem for the NP-completeness of minimizing swaps on trees (Theorem 4). The paper relies on this external result.
domain assumption Any tree can be embedded without crossings on any set of points in general position (Pach et al., 1991; Bose, 2002).
Used to justify that tree instances are always solvable, which motivates the bounded-swap question.
standard math Whether two segments with four distinct endpoints cross depends only on the order type of the endpoints.
Used in Lemma 8 and Theorem 9 to connect swap-equivalence to order type.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Geometry and Generation of a New Graph Planarity Game." pith.science (2026). https://pith.science/paper/JVKAAZDG

@misc{pith2026190801426,
  author       = {Pith},
  title        = {Pith review of: Geometry and Generation of a New Graph Planarity Game},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/JVKAAZDG}},
  note         = {Machine review of arXiv:1908.01426}
}

read the original abstract

We introduce a new abstract graph game, Swap Planarity, where the goal is to reach a state without edge intersections and a move consists of swapping the locations of two vertices connected by an edge. We analyze this puzzle game using concepts from graph theory and graph drawing, computational geometry, and complexity. Furthermore, we specify quality criteria for puzzle instances, and describe a method to generate high-quality instances. We also report on experiments that show how well this generation process works.

Figures

Figures reproduced from arXiv: 1908.01426 by the authors.

**Figure 2.** Six steps to solve an 8-cycle with one intersection. The edge to be swapped is [PITH_FULL_IMAGE:figures/full_fig_p003_2.png] view at source ↗

**Figure 3.** Positions and vertices for the lower bound construction. [PITH_FULL_IMAGE:figures/full_fig_p004_3.png] view at source ↗

Figures from the paper (12 more)

**Figure 4.** Figure 4: Bringing vj to pj using the bold path w1, w2, w3 (note that all plane embeddings must have vj at pj ). Left: initial situation. Middle: after swap (w1, w3). Right: after swap (w2, w3). Choose any vertex vj such that its removal will leave the graph connected. Suppose a…

**Figure 5.** Figure 5: The variable gadget. (a) Basic construction of input path of 7 vertices. (b–c) Two [PITH_FULL_IMAGE:figures/full_fig_p006_5.png]

**Figure 6.** Figure 6: (a) The split gadget and its two minimal planarizations: (b) the [PITH_FULL_IMAGE:figures/full_fig_p007_6.png]

**Figure 7.** Figure 7: The clause gadget with enlargement of the central construction. Thick edges must [PITH_FULL_IMAGE:figures/full_fig_p007_7.png]

**Figure 8.** Figure 8: A clause satisfied by the bottom-left variable. Thick edges are those that have been [PITH_FULL_IMAGE:figures/full_fig_p008_8.png]

**Figure 9.** Figure 9: Schematic representation of a complete construction for ( [PITH_FULL_IMAGE:figures/full_fig_p009_9.png]

**Figure 10.** Figure 10: Removing edges from the basic construction to turn the graph into a tree. [PITH_FULL_IMAGE:figures/full_fig_p010_10.png]

**Figure 11.** Figure 11: Region where a third point may not be placed if [PITH_FULL_IMAGE:figures/full_fig_p011_11.png]

**Figure 12.** Figure 12: Left figure, screenshot with the steps of the generation listed in sequence (Generate [PITH_FULL_IMAGE:figures/full_fig_p013_12.png]

**Figure 13.** Figure 13: Performance (total number of attempts to add a point to generate a complete [PITH_FULL_IMAGE:figures/full_fig_p014_13.png]

**Figure 14.** Figure 14: Number of points inside the convex hull as a function of the point set size, for dif [PITH_FULL_IMAGE:figures/full_fig_p015_14.png]

**Figure 15.** Figure 15: Standard deviation of the number of points inside the convex hull as a function of [PITH_FULL_IMAGE:figures/full_fig_p015_15.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

20 extracted references · 20 canonical work pages

[1]

Enumerating order types for small point sets with applications

Oswin Aichholzer, Franz Aurenhammer, and Hannes Krasser. Enumerating order types for small point sets with applications. Order, 19(3):265–281, 2002

work page 2002
[2]

On the number of plane geometric graphs

Oswin Aichholzer, Thomas Hackl, Clemens Huemer, Ferran Hurtado, Hannes Krasser, and Birgit Vogtenhuber. On the number of plane geometric graphs. Graphs and Combi- natorics, 23(1):67–84, 2007

work page 2007
[3]

On embedding an outer-planar graph in a point set

Prosenjit Bose. On embedding an outer-planar graph in a point set. Computational Geometry, 23(3):303–312, 2002

work page 2002
[4]

Prosenjit Bose, Vida Dujmovic, Ferran Hurtado, Stefan Langerman, Pat Morin, and David R. Wood. A polynomial bound for untangling geometric planar graphs. Discrete & Computational Geometry , 42(4):570–585, 2009

work page 2009
[5]

Planar embeddability of the vertices of a graph using a ﬁxed point set is NP-hard

Sergio Cabello. Planar embeddability of the vertices of a graph using a ﬁxed point set is NP-hard. Journal of Graph Algorithms and Applications , 10(2):353–363, 2006

work page 2006
[6]

A linear algorithm for embedding planar graphs using PQ-trees

Norishige Chiba, Takao Nishizeki, Shigenobu Abe, and Takao Ozawa. A linear algorithm for embedding planar graphs using PQ-trees. Journal of Computer and System Sciences , 30(1):54–76, 1985

work page 1985
[7]

Computational Geometry – Algorithms and Applications

Mark de Berg, Otfried Cheong, Marc van Kreveld, and Mark Overmars. Computational Geometry – Algorithms and Applications . Springer, Berlin, 3rd edition, 2008

work page 2008
[8]

How to draw a planar graph on a grid

Hubert De Fraysseix, J´ anos Pach, and Richard Pollack. How to draw a planar graph on a grid. Combinatorica, 10(1):41–51, 1990

work page 1990

Show all 20 references

[9]

Untangling a planar graph

Xavier Goaoc, Jan Kratochv´ ıl, Yoshio Okamoto, Chan-Su Shin, Andreas Spillner, and Alexander Wolﬀ. Untangling a planar graph. Discrete & Computational Geometry , 42(4):542–569, 2009

2009
[10]

Goodman and Richard Pollack

Jacob E. Goodman and Richard Pollack. Semispaces of conﬁgurations, cell complexes of arrangements. Journal of Combinatorial Theory, Series A , 37(3):257–293, 1984

1984
[11]

Arrangements

Dan Halperin and Micha Sharir. Arrangements. In Jacob E. Goodman, Joseph O’Rourke, and Csaba D. T´ oth, editors,Handbook of Discrete and Computational Geometry , pages 723–762. 3rd edition, 2018

2018
[12]

Minimum-weight triangulation is NP-hard

Wolfgang Mulzer and G¨ unter Rote. Minimum-weight triangulation is NP-hard. Journal of the ACM , 55(2):11:1–11:29, 2008. 18

2008
[13]

Every graph admits an unambiguous bold drawing

J´ anos Pach. Every graph admits an unambiguous bold drawing. In International Sym- posium on Graph Drawing , pages 332–342, 2011

2011
[14]

Embedding a planar triangulation with vertices at speciﬁed points

J´ anos Pach, Peter Gritzmann, Bojan Mohar, and Richard Pollack. Embedding a planar triangulation with vertices at speciﬁed points. The American Mathematical Monthly , 98(2):165–166, 1991

1991
[15]

Handbook of Graph Drawing and Visualization

Roberto Tamassia. Handbook of Graph Drawing and Visualization . CRC Press, 2013

2013
[16]

Planarity

John Tantalo. Planarity. http://planarity.net/, 2007. Accessed: 2018-05-25

2007
[17]

NetLogo: A simple environment for modeling complexity

Seth Tisue and Uri Wilensky. NetLogo: A simple environment for modeling complexity. In International Conference on Complex Systems , volume 21, pages 16–21, 2004

2004
[18]

Bold graph drawings

Marc van Kreveld. Bold graph drawings. Computational Geometry, 44(9):499–506, 2011

2011
[19]

On the obfuscation complexity of planar graphs

Oleg Verbitsky. On the obfuscation complexity of planar graphs. Theoretical Compututer Science, 396(1-3):294–300, 2008

2008
[20]

Demaine, Takehiro Ito, Jun Kawahara, Masashi Kiyomi, Yoshio Okamoto, Toshiki Saitoh, Akira Suzuki, Kei Uchizawa, and Takeaki Uno

Katsuhisa Yamanaka, Erik D. Demaine, Takehiro Ito, Jun Kawahara, Masashi Kiyomi, Yoshio Okamoto, Toshiki Saitoh, Akira Suzuki, Kei Uchizawa, and Takeaki Uno. Swap- ping labeled tokens on graphs. Theoretical Computer Science, 586:81–94, 2015. 19

2015

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.

[1] [1]

Enumerating order types for small point sets with applications

Oswin Aichholzer, Franz Aurenhammer, and Hannes Krasser. Enumerating order types for small point sets with applications. Order, 19(3):265–281, 2002

work page 2002

[2] [2]

On the number of plane geometric graphs

Oswin Aichholzer, Thomas Hackl, Clemens Huemer, Ferran Hurtado, Hannes Krasser, and Birgit Vogtenhuber. On the number of plane geometric graphs. Graphs and Combi- natorics, 23(1):67–84, 2007

work page 2007

[3] [3]

On embedding an outer-planar graph in a point set

Prosenjit Bose. On embedding an outer-planar graph in a point set. Computational Geometry, 23(3):303–312, 2002

work page 2002

[4] [4]

Prosenjit Bose, Vida Dujmovic, Ferran Hurtado, Stefan Langerman, Pat Morin, and David R. Wood. A polynomial bound for untangling geometric planar graphs. Discrete & Computational Geometry , 42(4):570–585, 2009

work page 2009

[5] [5]

Planar embeddability of the vertices of a graph using a ﬁxed point set is NP-hard

Sergio Cabello. Planar embeddability of the vertices of a graph using a ﬁxed point set is NP-hard. Journal of Graph Algorithms and Applications , 10(2):353–363, 2006

work page 2006

[6] [6]

A linear algorithm for embedding planar graphs using PQ-trees

Norishige Chiba, Takao Nishizeki, Shigenobu Abe, and Takao Ozawa. A linear algorithm for embedding planar graphs using PQ-trees. Journal of Computer and System Sciences , 30(1):54–76, 1985

work page 1985

[7] [7]

Computational Geometry – Algorithms and Applications

Mark de Berg, Otfried Cheong, Marc van Kreveld, and Mark Overmars. Computational Geometry – Algorithms and Applications . Springer, Berlin, 3rd edition, 2008

work page 2008

[8] [8]

How to draw a planar graph on a grid

Hubert De Fraysseix, J´ anos Pach, and Richard Pollack. How to draw a planar graph on a grid. Combinatorica, 10(1):41–51, 1990

work page 1990