Positive planar satisfiability problems under 3-connectivity constraints

DOI10.1016/J.TCS.2022.03.013MaRDI QIDQ2143145zbMATH OpenOpenAlexFDO

Authors Md. Manzurul Hasan, Debajyoti Mondal, Md. Saidur Rahman

Publication date 31 May 2022

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2108.12500

zbMATH Keywords

1-in-3-SATNAE 3-SATNP-hardplanar graphs

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Recommendations

• scientific article; zbMATH DE number 152108
• scientific article; zbMATH DE number 4094812
• Planar 3-SAT with a clause/variable cycle
• On strongly planar 3SAT
• Planar 3-SAT with a clause/variable cycle

Cites work

• A new proof of 3-colorability of Eulerian triangulations
• A simple algorithm for finding a maximum triangle-free 2-matching in subcubic graphs
• A special planar satisfiability problem and a consequence of its NP- completeness
• Basic graph theory
• Efficient algorithms for Petersen's matching theorem
• Hard tiling problems with simple tiles
• How to Draw a Graph
• scientific article; zbMATH DE number 4094812 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1953089 (Why is no real title available?)
• Maximum Cardinality Simple 2-matchings in Subcubic Graphs
• On Area-Optimal Planar Graph Drawings
• On strong NP-completeness of rational problems
• On the hardness of point-set embeddability (extended abstract)
• Planar 3-SAT with a clause/variable cycle
• Planar Formulae and Their Uses
• The complexity of satisfiability problems
• The complexity of theorem-proving procedures
• The Planar Hamiltonian Circuit Problem is NP-Complete
• Unifying maximum cut and minimum cut of a planar graph

Cited in

(2)

• Planar 3-SAT with a clause/variable cycle
• Relating planar graph drawings to planar satisfiability problems

This page was built for publication: Positive planar satisfiability problems under 3-connectivity constraints

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2143145)