{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,21]],"date-time":"2026-03-21T08:11:21Z","timestamp":1774080681912,"version":"3.50.1"},"reference-count":36,"publisher":"Elsevier BV","license":[{"start":{"date-parts":[[2026,5,1]],"date-time":"2026-05-01T00:00:00Z","timestamp":1777593600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2026,5,1]],"date-time":"2026-05-01T00:00:00Z","timestamp":1777593600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/legal\/tdmrep-license"},{"start":{"date-parts":[[2026,5,1]],"date-time":"2026-05-01T00:00:00Z","timestamp":1777593600000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-017"},{"start":{"date-parts":[[2026,5,1]],"date-time":"2026-05-01T00:00:00Z","timestamp":1777593600000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-037"},{"start":{"date-parts":[[2026,5,1]],"date-time":"2026-05-01T00:00:00Z","timestamp":1777593600000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-012"},{"start":{"date-parts":[[2026,5,1]],"date-time":"2026-05-01T00:00:00Z","timestamp":1777593600000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-029"},{"start":{"date-parts":[[2026,5,1]],"date-time":"2026-05-01T00:00:00Z","timestamp":1777593600000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-004"}],"content-domain":{"domain":["elsevier.com","sciencedirect.com"],"crossmark-restriction":true},"short-container-title":["Theoretical Computer Science"],"published-print":{"date-parts":[[2026,5]]},"DOI":"10.1016\/j.tcs.2026.115834","type":"journal-article","created":{"date-parts":[[2026,3,1]],"date-time":"2026-03-01T14:59:43Z","timestamp":1772377183000},"page":"115834","update-policy":"https:\/\/doi.org\/10.1016\/elsevier_cm_policy","source":"Crossref","is-referenced-by-count":0,"special_numbering":"C","title":["Linear Planar 3-SAT"],"prefix":"10.1016","volume":"1071","author":[{"ORCID":"https:\/\/orcid.org\/0009-0002-5675-8606","authenticated-orcid":false,"given":"Victorien","family":"Desbois","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8146-4429","authenticated-orcid":false,"given":"Ocan","family":"Sankur","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1228-4333","authenticated-orcid":false,"given":"Fran\u00e7ois","family":"Schwarzentruber","sequence":"additional","affiliation":[]}],"member":"78","reference":[{"key":"10.1016\/j.tcs.2026.115834_bib0001","series-title":"Computers and Intractability","volume":"29","author":"Garey","year":"2002"},{"issue":"2","key":"10.1016\/j.tcs.2026.115834_bib0002","doi-asserted-by":"crossref","first-page":"329","DOI":"10.1137\/0211025","article-title":"Planar formulae and their uses","volume":"11","author":"Lichtenstein","year":"1982","journal-title":"SIAM J. Comput."},{"issue":"2","key":"10.1016\/j.tcs.2026.115834_bib0003","doi-asserted-by":"crossref","first-page":"174","DOI":"10.1016\/0196-6774(86)90002-7","article-title":"Planar 3DM is NP-complete","volume":"7","author":"Dyer","year":"1986","journal-title":"J. Algorith."},{"key":"10.1016\/j.tcs.2026.115834_bib0004","doi-asserted-by":"crossref","first-page":"13","DOI":"10.1016\/j.tcs.2010.05.034","article-title":"The planar k-means problem is NP-hard","volume":"442","author":"Mahajan","year":"2012","journal-title":"Theor. Comput. Sci."},{"issue":"3","key":"10.1016\/j.tcs.2026.115834_bib0005","doi-asserted-by":"crossref","first-page":"729","DOI":"10.1137\/S0097539704371353","article-title":"The rectilinear Steiner arborescence problem is NP-complete","volume":"35","author":"Shi","year":"2005","journal-title":"SIAM J. Comput."},{"issue":"1","key":"10.1016\/j.tcs.2026.115834_bib0006","doi-asserted-by":"crossref","first-page":"33","DOI":"10.1109\/LRA.2015.2503143","article-title":"Intractability of optimal multirobot path planning on planar graphs","volume":"1","author":"Yu","year":"2015","journal-title":"IEEE Rob. Autom. Lett."},{"key":"10.1016\/j.tcs.2026.115834_bib0007","series-title":"Tatamibari is NP-complete","author":"Adler","year":"2020"},{"key":"10.1016\/j.tcs.2026.115834_bib0008","series-title":"CCCG","first-page":"28","article-title":"Sto-Stone is NP-Complete","author":"Allen","year":"2018"},{"key":"10.1016\/j.tcs.2026.115834_bib0009","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1016\/j.dam.2018.05.011","article-title":"Selecting and covering colored points","volume":"250","author":"Arkin","year":"2018","journal-title":"Discr. Appl. Math."},{"key":"10.1016\/j.tcs.2026.115834_bib0010","series-title":"Algorithmic Study of 2-Interval Graphs","author":"Simon","year":"2021"},{"key":"10.1016\/j.tcs.2026.115834_bib0011","series-title":"International Symposium on Algorithmics of Wireless Networks","first-page":"76","article-title":"Collision detection for modular robots-it is easy to cause collisions and hard to avoid them","author":"Gupta","year":"2024"},{"key":"10.1016\/j.tcs.2026.115834_bib0012","series-title":"Proceedings of the International Symposium on Combinatorial Search","first-page":"64","article-title":"Multi-agent path execution with uncertainty","volume":"17","author":"Liu","year":"2024"},{"key":"10.1016\/j.tcs.2026.115834_bib0013","doi-asserted-by":"crossref","first-page":"332","DOI":"10.1016\/j.tcs.2019.05.028","article-title":"Reconfiguration of satisfying assignments and subset sums: easy to find, hard to connect","volume":"806","author":"Cardinal","year":"2020","journal-title":"Theor. Comput. Sci."},{"issue":"12-14","key":"10.1016\/j.tcs.2026.115834_bib0014","doi-asserted-by":"crossref","first-page":"1054","DOI":"10.1016\/j.tcs.2010.12.005","article-title":"On the complexity of reconfiguration problems","volume":"412","author":"Ito","year":"2011","journal-title":"Theor. Comput. Sci."},{"key":"10.1016\/j.tcs.2026.115834_bib0015","series-title":"Computing and Combinatorics: 16th Annual International Conference, COCOON 2010, Nha Trang, Vietnam, July 19\u201321, 2010. Proceedings 16","first-page":"216","article-title":"Optimal binary space partitions in the plane","author":"de Berg","year":"2010"},{"key":"10.1016\/j.tcs.2026.115834_bib0016","series-title":"On simplified NP-complete variants of Not-All-Equal 3-SAT and 3-SAT","author":"Darmann","year":"2019"},{"issue":"06","key":"10.1016\/j.tcs.2026.115834_bib0017","doi-asserted-by":"crossref","first-page":"979","DOI":"10.1142\/S0129054118500168","article-title":"The monotone satisfiability problem with bounded variable appearances","volume":"29","author":"Darmann","year":"2018","journal-title":"Int. J. Found. Comput. Sci."},{"issue":"Discrete Algorithms","key":"10.1016\/j.tcs.2026.115834_bib0018","article-title":"Planar 3-SAT with a clause\/variable cycle","volume":"21","author":"Pilz","year":"2019","journal-title":"Discr. Math. Theor. Comput. Sci."},{"key":"10.1016\/j.tcs.2026.115834_bib0019","series-title":"Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA)","first-page":"1740","article-title":"On two-handed planar assembly partitioning with connectivity constraints","author":"Agarwal","year":"2021"},{"key":"10.1016\/j.tcs.2026.115834_bib0020","series-title":"Games, Puzzles, and Computation","author":"Hearn","year":"2009"},{"key":"10.1016\/j.tcs.2026.115834_bib0021","series-title":"41st International Symposium on Computational Geometry (SoCG 2025)","first-page":"1:1","article-title":"Reconfiguration of unit squares and disks: PSPACE-hardness in simple settings","volume":"332","author":"Abrahamsen","year":"2025"},{"issue":"1","key":"10.1016\/j.tcs.2026.115834_bib0022","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1016\/0166-218X(84)90081-7","article-title":"A simplified NP-complete satisfiability problem","volume":"8","author":"Tovey","year":"1984","journal-title":"Discr. Appl. Math."},{"key":"10.1016\/j.tcs.2026.115834_bib0023","series-title":"50 Years of Integer Programming 1958\u20132008: from the Early Years to the State-of-the-Art","first-page":"219","article-title":"Reducibility among combinatorial problems","author":"Karp","year":"2009"},{"issue":"1","key":"10.1016\/j.tcs.2026.115834_bib0024","doi-asserted-by":"crossref","first-page":"271","DOI":"10.4064\/fm-15-1-271-283","article-title":"Sur le probleme des courbes gauches en topologie","volume":"15","author":"Kuratowski","year":"1930","journal-title":"Fundamenta Mathematicae"},{"issue":"4","key":"10.1016\/j.tcs.2026.115834_bib0025","doi-asserted-by":"crossref","first-page":"549","DOI":"10.1145\/321850.321852","article-title":"Efficient planarity testing","volume":"21","author":"Hopcroft","year":"1974","journal-title":"J. ACM (JACM)"},{"key":"10.1016\/j.tcs.2026.115834_bib0026","article-title":"The complexity of the Hamiltonian circuit problem for maximal planar graphs","volume":"298","author":"Wigderson","year":"1982","journal-title":"EECS Department Report"},{"key":"10.1016\/j.tcs.2026.115834_bib0027","doi-asserted-by":"crossref","first-page":"327","DOI":"10.1007\/s00407-013-0127-z","article-title":"On the history of the Euclidean Steiner tree problem","volume":"68","author":"Brazil","year":"2014","journal-title":"Arch. Hist. Exact Sci."},{"key":"10.1016\/j.tcs.2026.115834_bib0028","series-title":"Technical Report","article-title":"Two-Page Book Embedding And Clustered Graph Planarity","author":"Hong","year":"2009"},{"key":"10.1016\/j.tcs.2026.115834_bib0029","series-title":"Linear Planar 3-SAT and Its Applications in Planning","volume":"abs\/2506.14713","author":"Desbois","year":"2025"},{"issue":"2","key":"10.1016\/j.tcs.2026.115834_bib0030","doi-asserted-by":"crossref","first-page":"1888","DOI":"10.1109\/LRA.2025.3526564","article-title":"Spanning-tree based coverage for a tethered robot","volume":"10","author":"Peng","year":"2025","journal-title":"IEEE Robotics Autom. Lett."},{"key":"10.1016\/j.tcs.2026.115834_bib0031","doi-asserted-by":"crossref","first-page":"191","DOI":"10.1613\/jair.1.11864","article-title":"The parameterized complexity of motion planning for snake-like robots","volume":"69","author":"Gupta","year":"2020","journal-title":"J. Artif. Intell. Res."},{"key":"10.1016\/j.tcs.2026.115834_bib0032","series-title":"Graph Theory (on Demand Printing of 02787)","author":"Harary","year":"2018"},{"key":"10.1016\/j.tcs.2026.115834_bib0033","article-title":"Flatworlds: optimization algorithms for planar graphs","author":"Klein","year":"2011","journal-title":"Draft available online at http:\/\/www. planarity. org"},{"key":"10.1016\/j.tcs.2026.115834_bib0034","series-title":"International Colloquium on Automata, Languages, and Programming","first-page":"576","article-title":"A dynamic data structure for planar graph embedding","author":"Tamassia","year":"1988"},{"issue":"2","key":"10.1016\/j.tcs.2026.115834_bib0035","doi-asserted-by":"crossref","first-page":"217","DOI":"10.1016\/0304-3975(78)90051-8","article-title":"Finding the intersection of two convex polyhedra","volume":"7","author":"Muller","year":"1978","journal-title":"Theor. Comput. Sci."},{"key":"10.1016\/j.tcs.2026.115834_bib0036","series-title":"A Course in Combinatorics","author":"Van Lint","year":"2001"}],"container-title":["Theoretical Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0304397526000939?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0304397526000939?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2026,3,21]],"date-time":"2026-03-21T07:36:28Z","timestamp":1774078588000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0304397526000939"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,5]]},"references-count":36,"alternative-id":["S0304397526000939"],"URL":"https:\/\/doi.org\/10.1016\/j.tcs.2026.115834","relation":{},"ISSN":["0304-3975"],"issn-type":[{"value":"0304-3975","type":"print"}],"subject":[],"published":{"date-parts":[[2026,5]]},"assertion":[{"value":"Elsevier","name":"publisher","label":"This article is maintained by"},{"value":"Linear Planar 3-SAT","name":"articletitle","label":"Article Title"},{"value":"Theoretical Computer Science","name":"journaltitle","label":"Journal Title"},{"value":"https:\/\/doi.org\/10.1016\/j.tcs.2026.115834","name":"articlelink","label":"CrossRef DOI link to publisher maintained version"},{"value":"article","name":"content_type","label":"Content Type"},{"value":"\u00a9 2026 Elsevier B.V. All rights are reserved, including those for text and data mining, AI training, and similar technologies.","name":"copyright","label":"Copyright"}],"article-number":"115834"}}