Pith. sign in

REVIEW 2 major objections 5 minor 34 references

Linear Planar 3-SAT and Its Applications in Planning

T0 review · 2 major / 5 minor · reviewed 2026-08-15 · deepseek-v4-flash

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

Pith's one-line read Combining linearity and planarity in 3-SAT preserves NP-completeness and PSPACE-completeness, and the new fragments settle the complexity of connected multi-agent pathfinding on 2D grids.

desk verdict Solid new 3-SAT fragments and a useful cycle-augmentation toolkit, but the 2D CMAPF PSPACE-hardness proof has a load-bearing reachability gap that needs a real proof. read the letter →

arxiv 2506.14713 v1 pith:WFCMEIAF submitted 2025-06-17 cs.CC

Victorien Desbois , Ocan Sankur , François Schwarzentruber This is my paper · ORCID
classification cs.CC MSC 68Q1768Q2503B05
keywords linearplanar3-SATliteral-planarmonotonereconfigurationcycleaugmentationconnectedmulti-agentpathfindingPSPACE-completenessNP-completeness
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

The paper asks whether the two most useful SAT restrictions for planning, linearity and planarity, can be combined without losing hardness, and answers yes. It introduces linear planar 3-SAT and the stricter linear literal-planar 3-SAT, proves both NP-complete, and proves their reconfiguration problems PSPACE-complete, using a new monotone linear planar fragment as an intermediate. These results are then applied to connected multi-agent pathfinding on 2D grids, a setting where only the 3D case had previously been settled: the bounded version is NP-complete even with execution bound 2 and communication radius 1, and the unbounded version is PSPACE-complete. A reader should care because the new SAT fragments are designed to make hardness proofs for planar, grid-based planning problems substantially more direct.

What carries the argument

The argument is carried by three mechanisms. First, the SAT reduction machinery: to make a monotone planar formula linear, each variable occurrence is replaced by a fresh literal connected through chains of two-literal clauses, and linear literal-planar formulas are turned into monotone linear planar formulas by renaming each negative literal to a fresh variable and adding a paired two-literal clause. Second, the planar cycle augmentation theory: a sufficient condition, the existence of a kite-graph, a bipartite planar Eulerian graph in which each target vertex has degree 2, guarantees a cycle over the target vertices that can be added while preserving planarity, and when the instance has a dually connected matching such a cycle is computable in polynomial time; this is what lets the reconfiguration reduction build the literal cycle that prior planar reconfiguration results lacked. Third, the CMAPF gadget architecture: variable agents encode truth values by position, mobile literal agents in clause gadgets can move only when their literal is satisfied, and the bridge agents on the variable line enforce that at most one variable flips per step.

What would settle it

Search the state space of the variable-gadget line in Figure 24, restricted to configurations with all variable agents set and at most one free bridge agent, for a configuration that cannot be reached from the initial configuration without first freeing two bridge agents; exhibiting such a configuration would refute Claim 8.10 and break the PSPACE-hardness reduction.

Watch

Extended reading notes

Core claim

The discovery is that the linear and planar restrictions on 3-CNF formulas are compatible in a strong sense: formulas that are simultaneously linear and planar, with respect to a variable cycle, and in the stricter literal-planar variant with respect to a literal cycle, remain NP-complete for satisfiability, and their reconfiguration problems are PSPACE-complete. The intermediate monotone linear planar fragment is also NP- and PSPACE-complete, and the NP-hardness holds even when each variable appears negatively in at most one clause. The paper applies these fragments to grid planning: it proves that Bounded 2D CMAPF is NP-complete even for bound 2 and radius 1, and that 2D CMAPF is PSPACE-complete. Supporting this chain, it shows that planar cycle augmentation is NP-complete but admits a polynomial-time sufficient condition based on kite-graphs and dually connected matchings.

Load-bearing premise

The PSPACE-hardness application rests on Claim 8.10's assertion that every configuration with all variable agents set can be reached from the initial configuration, and hence that any chosen bridge agent can be freed; the paper demonstrates this only from the initial configuration, leaving unsupported the equivalence between CMAPF moves and single variable flips claimed in Claim 8.12.

Editorial extensions

If this is right

  • If the proofs are correct, Linear Planar 3-SAT is NP-complete, giving a planar and linear SAT fragment that can serve as a source for hardness reductions to planar motion-planning problems.
  • Linear Literal-Planar 3-SAT reconfiguration is PSPACE-complete, and so is its monotone linear planar restriction even when each negative literal appears in at most one clause.
  • Bounded 2D CMAPF is NP-complete even with execution bound 2 and communication radius 1, so the hardness of the bounded problem does not require long paths or long-range communication.
  • Unbounded 2D CMAPF is PSPACE-complete, settling the 2D case left open by prior work that only handled 3D grids.
  • Because the constructed gadgets trap each agent in its own connected component, the same hardness transfers to the anonymous version of CMAPF in which targets are not assigned to specific agents.

Reading between the lines

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

  • Inference: the same friend-assignment technique used to reduce linear literal-planar reconfiguration to monotone linear planar reconfiguration could likely prove PSPACE-completeness for a monotone literal-planar fragment, a variant the paper does not define.
  • Inference: the kite-graph and dually-connected-matching criterion suggests a polynomial-time algorithm for planar cycle augmentation on graph classes that reliably admit such matchings; testing outerplanar or bounded-treewidth graphs would be a direct next step.
  • Inference: because the 2D hardness survives radius 1 and bound 2, the geometry of the 2D grid rather than the communication range is the source of hardness; whether the reduction adapts to hexagonal or king-move grids is a testable extension not addressed in the paper.
  • Inference: if the missing reachability proof in Claim 8.10 is supplied, the same bridge-gadget architecture should extend to other connectivity-constrained motion planning problems, such as the tethered-robot and snake-like robot settings named in the paper.
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.

Referee Report

2 major / 5 minor

Summary. The paper introduces two new fragments of 3-SAT, Linear Planar 3-SAT and Linear Literal-Planar 3-SAT, and proves that the satisfiability problems for both fragments are NP-complete. It then proves PSPACE-completeness for the corresponding reconfiguration problems, via reductions from NCL and from known planar 3-SAT reconfiguration results, using a new theory of planar cycle augmentation and dually connected matchings. The main applications are complexity classifications of Connected Multi-Agent Pathfinding on two-dimensional grids: Bounded 2D CMAPF is claimed NP-complete even with bound 2 and radius 1, and unbounded 2D CMAPF is claimed PSPACE-complete.

Significance. If the proofs are completed as claimed, the results are significant: they settle the complexity of 2D CMAPF, left open in earlier work, and provide new SAT fragments that may be useful for planar and linear planning reductions. The paper also develops an interesting self-contained theory of planar cycle augmentation and kite-graphs. Strengths include explicit, mostly detailed reduction chains, an extensive appendix on planar graph operations, and clear statements separating new results from prior work. The main deficits are concentrated in the most intricate gadget argument, Claim 8.10, and in a definitional inconsistency in Section 7; both are load-bearing for the PSPACE-hardness application.

major comments (2)
  1. [§8.4, Claim 8.10(2)] The proof of Point 2 first gives a procedure from the initial configuration of Figure 24 and then asserts: "We proved that c can be reached from the initial configuration." No proof of this assertion is given for an arbitrary variable-set configuration c, and this reachability is exactly what is needed in Claim 8.12, where a flip must be simulated from an arbitrary configuration reached after earlier flips. The reversibility of CMAPF does not help unless every such c is first shown reachable from the initial configuration. As written, the equivalence between CMAPF executions and variable-flip sequences is unsupported, so Theorem 8.8 rests on an unproved claim. The counting argument in Point 1 also does not by itself establish uniqueness of a free agent: |A| = 2|V|-1 and 2|V|-2 requesters show that if not all agents are adjacent to requesters then at least one agent is not, but they do not rule out several simultaneously movable agents. A complete proof of both points, or a revised simulation that avoids them, is required.
  2. [§7, Lemma 7.5 and Definition 2.2] Lemma 7.5 defines E' = {(l,¬l) | (l,¬l) ∈ E} as the "set of paired literals" in G_lit(ϕ). However, Definition 2.2 defines G_lit(ϕ) as a bipartite graph with only literal-clause edges; paired edges between opposite literals are introduced only later in Definition 3.2 as part of G_lit(ϕ,π). Thus either the graph used in Lemma 7.5 contains edges not present in the graph defined earlier, in which case the cycle augmentation instance is not on the stated graph, or E' is empty and the dually connected matching argument cannot even get started. This discrepancy needs to be fixed explicitly, for example by defining the augmented literal graph used in the Section 7 reduction and checking that Lemma 7.5 refers to that graph.
minor comments (5)
  1. [§3.1, Eq. (1)] The clause list in formula (1) ends with (g∨h∨j) but the third negative clause is written (¬c∨¬f∨¬i); the variable should likely be j for consistency.
  2. [§3.1, after Prop. 3.2] The text says "Theorem 3.2 shows that Planar Linear 3-SAT has strictly less possible inputs" but Proposition 3.2 is the correct reference; the same numbering slip appears elsewhere.
  3. [§7.1, before Lemma 7.2] The sentence "We set ν:=ν_s and ν:=ν_t" should define ν' as ν_t; otherwise the target assignment is overwritten.
  4. [§4.2, proof of Theorem 4.6] In the final sentence of the proof, "Therefore G_lit(ϕ,π) is planar and valid" should refer to the constructed variable-clause graph G_var(ϕ',π'), not to G_lit(ϕ,π).
  5. [§8.3, Claim 8.6 proof] The proof says "Similar to the proof of Theorem 8.6" but the claim being proved is Claim 8.6; the intended reference should be corrected.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the new hardness results reduce from external NCL/C2C and monotone planar 3-SAT, and the cited self-work is contextual only.

full rationale

The paper's derivation chain is rooted in external results, not in its own conclusions. The NP-hardness chain starts from Monotone Planar 3-SAT [16] (external), reduces to Linear Literal-Planar 3-SAT with explicit equisatisfiability proofs, then to Monotone Linear Planar 3-SAT, and finally yields Linear Planar 3-SAT NP-completeness. The PSPACE-hardness chain starts from NCL C2C [17] and the planar 3-SAT reconfiguration construction of [13], both external; the authors then prove that the constructed formula is linear literal-planar, using their own cycle-augmentation theorem (Theorem 5.12) which is proved internally via kite graphs and planar duality rather than assumed. The CMAPF reductions are likewise built on the newly proved NP- and PSPACE-complete 3-SAT fragments, whose hardness in turn comes from external sources. The self-citations that appear ([15], [24]) are used only as context or motivation, for example noting that the 2D case was left open in [15]; they are not load-bearing inputs to the new reductions. No fitted parameter is renamed as a prediction, no known result is repackaged as a new one, and no uniqueness theorem from prior author work is invoked to force a choice. The gap identified by a skeptical reader in Claim 8.10(2) — that reachability of arbitrary all-variables-set configurations from the initial bridge-line configuration is asserted rather than proved — is a correctness/completeness concern about the CMAPF gadget proof, not a circularity: even if that gap exists, the claimed derivation does not reduce to its own inputs by definition or by self-citation. The paper is therefore self-contained against external benchmarks for the purposes of circularity analysis.

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

The central results require no numerical free parameters. The only inputs are combinatorial constructions and theorems adopted from prior work. The paper's internal inventions are mathematical conditions justified by proofs rather than by empirical fit.

assumptions (4)
  • standard math Kuratowski's theorem: a graph is planar iff it has no subdivision of K5 or K3,3.
    Used in Proposition 3.2 to prove that the linear formula phi has a subdivision of K3,3 as its variable-clause graph and is therefore nonplanar.
  • standard math Planar graph duality facts: the dual of a connected planar graph is connected; an Eulerian connected planar graph has a bipartite dual; vertex relaxation and edge deletion preserve planarity and connectivity.
    These facts are invoked throughout Section 5 and the appendix to justify Algorithm 1 and the kite-graph theorems.
  • domain assumption External NP- and PSPACE-completeness results: Monotone Planar 3-SAT is NP-complete [16], NCL C2C is PSPACE-complete [17], and planar 3-SAT reconfiguration is PSPACE-complete [13].
    Adopted without proof as the bases of the reductions in Sections 4 and 7.
  • domain assumption Hamiltonian cycle detection in maximal planar graphs is NP-complete
    Used in Theorem 5.2 to prove NP-hardness of planar cycle augmentation.
invented entities (2)
  • Kite graph K_I
    purpose: A bipartite witness that enables polynomial-time construction of a V'-cycle preserving planarity in planar cycle augmentation.
    Introduced in Definition 5.3 and verified internally by Theorem 5.4; no empirical prediction outside the paper.
  • Dually connected matching
    purpose: A tractable sufficient condition under which a V'-cycle can be computed in polynomial time and used to build literal cycles.
    Defined and proved internally in Theorem 5.12; used in Lemma 7.5 for the reconfiguration hardnes results.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Linear Planar 3-SAT and Its Applications in Planning." pith.science (2026). https://pith.science/paper/WFCMEIAF

@misc{pith2026250614713,
  author       = {Pith},
  title        = {Pith review of: Linear Planar 3-SAT and Its Applications in Planning},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/WFCMEIAF}},
  note         = {Machine review of arXiv:2506.14713}
}
read the original abstract

Several fragments of the satisfiability problem have been studied in the literature. Among these, Linear 3-SAT is a satisfaction problem in which each clause (viewed as a set of literals) intersects with at most one other clause; moreover, any pair of clauses have at most one literal in common. Planar 3-SAT is a fragment which requires that the so-called variable-clause graph is planar. Both fragments are NP-complete and have applications in encoding NP-hard planning problems. In this paper, we investigate the complexity and applications of the fragment obtained combining both features. We define Linear Planar 3-SAT and prove its NP-completeness. We also study the reconfiguration problem of Linear Planar 3-SAT and show that it is PSPACE-complete. As an application, we use these new results to prove the NP-completeness of Bounded Connected Multi-Agent Pathfinding and the PSPACE-completeness of Connected Multi-Agent Pathfinding in two-dimensional grids.

Figures

Figures reproduced from arXiv: 2506.14713 by the authors.

Figure 1
Figure 1. NP-complete 3-SAT problems, and the NP-completeness of bounded grid CMAPF. Prob [PITH_FULL_IMAGE:figures/full_fig_p004_1.png] view at source ↗
Figure 2
Figure 2. PSPACE-complete of reconfiguration problems. [PITH_FULL_IMAGE:figures/full_fig_p005_2.png] view at source ↗
Figure 3
Figure 3. Literal-clause graph (up) and variable-clause graph (down) of the CNF formula ( [PITH_FULL_IMAGE:figures/full_fig_p006_3.png] view at source ↗
Figures from the paper (27 more)
Figure 4
Figure 4. Figure 4: Variable-clause graph Gvar(ϕ, π) augmented with variable cycle (a, b, c, d) for the planar 3-CNF formula (¬a ∨ b ∨ ¬c) ∧ (a ∨ c ∨ ¬d) ∧ (a ∨ ¬b ∨ ¬d) ∧ (b ∨ c ∨ ¬d) Definition 2.5 (Variable Cycle). A variable cycle π is a permutation xπ1 , . . . , xπn of a given sequen…
Figure 5
Figure 5. Figure 5: Variable-clause graph of the monotone planar 3-CNF formula ( [PITH_FULL_IMAGE:figures/full_fig_p008_5.png]
Figure 6
Figure 6. Figure 6: Variable-clause graph of the planar linear 3-CNF formula ( [PITH_FULL_IMAGE:figures/full_fig_p009_6.png]
Figure 7
Figure 7. Figure 7: Variable-clause graph Gvar(ϕ) of the linear formula ϕ, which is a subdivision of K3,3. Proof. Formula ϕ is a linear since there are three unique literals per clause so there is no intersection between any pair clauses. The graph Gvar(ϕ) is given in [PITH_FULL_IMAGE:fi…
Figure 8
Figure 8. Figure 8: Literal-clause graph Glit(ϕ, π) augmented with the literal cycle (a, ¬b, b,¬c, d, ¬d, c, ¬a) and paired edges. As this graph is planar, and that paired edges are inside π and the clauses are outside π in the shown embedding, the corresponding formula ϕ is paired-litera…
Figure 9
Figure 9. Figure 9: Construction of Glit(ϕ ′ , π′ ) from Gvar(ϕ, π), by replacing each variable v from a Monotone Planar 3-SAT instance ϕ by the gadgets Gv and G¯ v. replacement of node v by Glit(ϕ ′ v ). A planar embedding for Glit(ϕ ′ v ) is given in Figure 9c where the literals appear …
Figure 10
Figure 10. Figure 10: From the literal-clause graph Glit(ϕ, π), we construct the planar variable-clause graph Gvar(ϕ ′ , π′ ) obtained as follows: we replace each negative literals ¬x by x ′ , and each paired edge x ¬x a clause ¬x ′ ∨ ¬x ′ . This is used in the reduction given in Theorem 4…
Figure 11
Figure 11. Figure 11: Positive instance of planar cycle augmentation with [PITH_FULL_IMAGE:figures/full_fig_p019_11.png]
Figure 12
Figure 12. Figure 12: A planar embedding of G ∪ KI with I = (G, {g, b, j, h}). The graph G is shown in plain edges, and the kite-graph is shown in dashed edges. We say that a cycle π separates two sets of edges E ′ and E ′′ in an embedding if all edges in E ′ are in the interior of π and a…
Figure 13
Figure 13. Figure 13: Execution of the algorithm. The algorithm starts with an embedding of [PITH_FULL_IMAGE:figures/full_fig_p021_13.png]
Figure 14
Figure 14. Figure 14: An instance, a dually connected matching, and the corresponding kite-graph. [PITH_FULL_IMAGE:figures/full_fig_p025_14.png]
Figure 15
Figure 15. Figure 15: Nondeterministic constraint logic (NCL). A constraint graph contains OR nodes (a) and [PITH_FULL_IMAGE:figures/full_fig_p028_15.png]
Figure 16
Figure 16. Figure 16: Gadgets of the reduction from C2C to Linear Literal-Planar 3-SAT Reconfiguration (as [PITH_FULL_IMAGE:figures/full_fig_p030_16.png]
Figure 17
Figure 17. Figure 17: Example of a transformation of a Configuration To Configuration instance to a Linear [PITH_FULL_IMAGE:figures/full_fig_p031_17.png]
Figure 18
Figure 18. Figure 18: NP-hardness: Gadget for a variable. provides connectivity to the top requester wire • • • • • if x is true, and to the bottom requester wire otherwise. Split Part. The split gadget SPLITx is presented in Figure 18d. As shown in Figure 18b, it is placed above the switc…
Figure 19
Figure 19. Figure 19: NP-hardness: gadget for a clause. Clause Gadget [PITH_FULL_IMAGE:figures/full_fig_p038_19.png]
Figure 20
Figure 20. Figure 20: NP-hardness: overall idea of the reduction. [PITH_FULL_IMAGE:figures/full_fig_p039_20.png]
Figure 21
Figure 21. Figure 21: A variable x in Gvar(ϕ, π) is replaced by BRIDGEx and SWITCHx. Split Part. The gadget SPLITx is given in Figure 21d and is nearly the same as the one used in th proof of Theorem 8.3 (see Figure 18d). The only difference resides in the fact that now the source and targ…
Figure 22
Figure 22. Figure 22: Clause gadget for showing the PSPACE-hardness. [PITH_FULL_IMAGE:figures/full_fig_p044_22.png]
Figure 23
Figure 23. Figure 23: Showing the PSPACE-hardness: overall transformation of [PITH_FULL_IMAGE:figures/full_fig_p045_23.png]
Figure 24
Figure 24. Figure 24: Illustration of the line of variable gadgets. All the agents are on their respective target [PITH_FULL_IMAGE:figures/full_fig_p045_24.png]
Figure 25
Figure 25. Figure 25: A planar embedding of the graph G = (V, E). Example A.4. Figure 25a depicts the planar embedding ΓG = {F 1 , F2 , F ∞} with F 1 = (uv, vw, vw, vx, xy, yu) F 2 = (vz, zx, vx) F ∞ = (uv, yu, yx, zx, vz) Each edge indeed appears twice. For instance, uv touches F 1 and F …
Figure 26
Figure 26. Figure 26: Construction of the sequence of edges in clockwise order around [PITH_FULL_IMAGE:figures/full_fig_p054_26.png]
Figure 27
Figure 27. Figure 27: Edge addition and edge deletion. We recall here that [PITH_FULL_IMAGE:figures/full_fig_p055_27.png]
Figure 28
Figure 28. Figure 28: Vertex relaxation and edge contraction. Vertex relaxation of vertex [PITH_FULL_IMAGE:figures/full_fig_p056_28.png]
Figure 29
Figure 29. Figure 29: The dual operations of vertex relaxation and edge contraction are respectively edge [PITH_FULL_IMAGE:figures/full_fig_p056_29.png]
Figure 30
Figure 30. Figure 30: Edge subdivision and edge smoothing. Edge subdivision consists in adding a middle [PITH_FULL_IMAGE:figures/full_fig_p057_30.png]

Review history (2 revisions) →

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

34 extracted references · 32 canonical work pages

  1. [15]

    Calviac, O

    I. Calviac, O. Sankur, F. Schwarzentruber, Improved complexity results and an efficient solution for connected multi-agent path finding, in: AAMAS 2023-22nd International Conference on Autonomous Agents and Multiagent Systems, 2023, pp. 1–9

    work page 2023

  2. [1]

    M. R. Garey, D. S. Johnson, Computers and intractability, Vol. 29, wh freeman New York, 2002

    work page 2002

  3. [2]

    Lichtenstein, Planar formulae and their uses, SIAM journal on computing 11 (2) (1982) 329–343

    D. Lichtenstein, Planar formulae and their uses, SIAM journal on computing 11 (2) (1982) 329–343

    work page 1982

  4. [3]

    M. E. Dyer, A. M. Frieze, Planar 3dm is np-complete, Journal of Algorithms 7 (2) (1986) 174–184

    work page 1986

  5. [4]

    Mahajan, P

    M. Mahajan, P. Nimbhorkar, K. Varadarajan, The planar k-means problem is np-hard, Theoretical computer science 442 (2012) 13–21

    work page 2012

  6. [5]

    W. Shi, C. Su, The rectilinear steiner arborescence problem is np-complete, SIAM Journal on Computing 35 (3) (2005) 729–740

    work page 2005

  7. [6]

    Yu, Intractability of optimal multirobot path planning on planar graphs, IEEE Robotics and Automation Letters 1 (1) (2015) 33–40

    J. Yu, Intractability of optimal multirobot path planning on planar graphs, IEEE Robotics and Automation Letters 1 (1) (2015) 33–40

    work page 2015

  8. [7]

    Tatamibari is NP-complete

    A. Adler, J. Bosboom, E. D. Demaine, M. L. Demaine, Q. C. Liu, J. Lynch, Tatamibari is np-complete, arXiv preprint arXiv:2003.08331 (2020)

    work page Pith review arXiv 2020

Show all 34 references
  1. [8]

    Allen, A

    A. Allen, A. Williams, Sto-stone is np-complete., in: CCCG, 2018, pp. 28–34. 48

    2018

  2. [9]

    E. M. Arkin, A. Banik, P. Carmi, G. Citovsky, M. J. Katz, J. S. Mitchell, M. Simakov, Selecting and covering colored points, Discrete Applied Mathe- matics 250 (2018) 75–86

    2018

  3. [10]

    Simon, Algorithmic study of 2-interval graphs, Ph.D

    A. Simon, Algorithmic study of 2-interval graphs, Ph.D. thesis, Master thesis, Delft University of Technology (2021)

    2021

  4. [11]

    Gupta, M

    S. Gupta, M. van Kreveld, O. Michail, A. Padalkin, Collision detection for mod- ular robots-it is easy to cause collisions and hard to avoid them, in: International Symposium on Algorithmics of Wireless Networks, Springer, 2024, pp. 76–90

    2024

  5. [12]

    Y. Liu, X. Tang, W. Cai, J. Li, Multi-agent path execution with uncertainty, in: Proceedings of the International Symposium on Combinatorial Search, Vol. 17, 2024, pp. 64–72

    2024

  6. [13]

    Cardinal, E

    J. Cardinal, E. D. Demaine, D. Eppstein, R. A. Hearn, A. Winslow, Reconfigu- ration of satisfying assignments and subset sums: Easy to find, hard to connect, Theoretical Computer Science 806 (2020) 332–343

    2020

  7. [14]

    T. Ito, E. D. Demaine, N. J. Harvey, C. H. Papadimitriou, M. Sideri, R. Uehara, Y. Uno, On the complexity of reconfiguration problems, Theoretical Computer Science 412 (12-14) (2011) 1054–1065

    2011

  8. [16]

    de Berg, A

    M. de Berg, A. Khosravi, Optimal binary space partitions in the plane, in: Com- puting and Combinatorics: 16th Annual International Conference, COCOON 2010, Nha Trang, Vietnam, July 19-21, 2010. Proceedings 16, Springer, 2010, pp. 216–225

    2010

  9. [17]

    R. A. Hearn, E. D. Demaine, Games, puzzles, and computation, CRC Press, 2009

    2009

  10. [18]

    Li, Efficient and effective techniques for large-scale multi-agent path finding, Ph.D

    J. Li, Efficient and effective techniques for large-scale multi-agent path finding, Ph.D. thesis, University of Southern California (2022)

    2022

  11. [19]

    Tateo, J

    D. Tateo, J. Banfi, A. Riva, F. Amigoni, A. Bonarini, Multiagent connected path planning: Pspace-completeness and how to deal with it 32 (1) (2018). 49

    2018

  12. [20]

    Kuratowski, Sur le probleme des courbes gauches en topologie, Fundamenta mathematicae 15 (1) (1930) 271–283

    C. Kuratowski, Sur le probleme des courbes gauches en topologie, Fundamenta mathematicae 15 (1) (1930) 271–283

    1930

  13. [21]

    Hopcroft, R

    J. Hopcroft, R. Tarjan, Efficient planarity testing, Journal of the ACM (JACM) 21 (4) (1974) 549–568

    1974

  14. [22]

    Wigderson, The complexity of the hamiltonian circuit problem for maximal planar graphs, EECS Department Report 298 (1982)

    A. Wigderson, The complexity of the hamiltonian circuit problem for maximal planar graphs, EECS Department Report 298 (1982)

    1982

  15. [23]

    G. A. Hollinger, S. Singh, Multirobot coordination with periodic connectivity: Theory and experiments, IEEE Trans. Robotics 28 (4) (2012) 967–973.doi: 10.1109/TRO.2012.2190178. URLhttps://doi.org/10.1109/TRO.2012.2190178

    2012

  16. [24]

    Charrier, A

    T. Charrier, A. Queffelec, O. Sankur, F. Schwarzentruber, Complexity of plan- ning for connected agents, Auton. Agents Multi Agent Syst. 34 (2) (2020) 44. doi:10.1007/S10458-020-09468-5. URLhttps://doi.org/10.1007/s10458-020-09468-5

    2020 doi

  17. [25]

    Schnyder, Embedding planar graphs on the grid, in: Proceedings of the first annual ACM-SIAM symposium on Discrete algorithms, 1990, pp

    W. Schnyder, Embedding planar graphs on the grid, in: Proceedings of the first annual ACM-SIAM symposium on Discrete algorithms, 1990, pp. 138–148

    1990

  18. [26]

    Brazil, R

    M. Brazil, R. L. Graham, D. A. Thomas, M. Zachariasen, On the history of the euclidean steiner tree problem, Archive for history of exact sciences 68 (2014) 327–354

    2014

  19. [27]

    S.-H. Hong, H. Nagamochi, Two-page book embedding and clustered graph planarity, Tech. rep., Citeseer (2009)

    2009

  20. [28]

    X. Peng, F. Schwarzentruber, O. Simonin, C. Solnon, Spanning-tree based cover- age for a tethered robot, IEEE Robotics Autom. Lett. 10 (2) (2025) 1888–1895. doi:10.1109/LRA.2025.3526564. URLhttps://doi.org/10.1109/LRA.2025.3526564

    2025

  21. [29]

    Gupta, G

    S. Gupta, G. Sa’ar, M. Zehavi, The parameterized complexity of motion plan- ning for snake-like robots, J. Artif. Intell. Res. 69 (2020) 191–229.doi: 10.1613/JAIR.1.11864. URLhttps://doi.org/10.1613/jair.1.11864

    2020 doi

  22. [30]

    Harary, Graph theory (on Demand Printing of 02787), CRC Press, 2018

    F. Harary, Graph theory (on Demand Printing of 02787), CRC Press, 2018. 50

    2018

  23. [31]

    P. N. Klein, Flatworlds: Optimization algorithms for planar graphs, Draft avail- able online at http://www. planarity. org (2011)

    2011

  24. [32]

    Tamassia, A dynamic data structure for planar graph embedding, in: In- ternational Colloquium on Automata, Languages, and Programming, Springer, 1988, pp

    R. Tamassia, A dynamic data structure for planar graph embedding, in: In- ternational Colloquium on Automata, Languages, and Programming, Springer, 1988, pp. 576–590

    1988

  25. [33]

    D. E. Muller, F. P. Preparata, Finding the intersection of two convex polyhedra, Theoretical Computer Science 7 (2) (1978) 217–236

    1978

  26. [34]

    J. H. Van Lint, R. M. Wilson, A course in combinatorics, Cambridge university press, 2001. A. Definitions and properties of planar graphs In order to make our paper self-contained, we recall some properties of planar graphs that are used in Section 5. Some of these results can...

    2001

Pith tools

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