Positive planar satisfiability problems under 3-connectivity constraints

DOI10.1016/j.tcs.2022.03.013OpenAlexW3196411836MaRDI QIDQ2143145

Debajyoti Mondal, Md. Manzurul Hasan, 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

planar graphsNP-hard1-in-3-SATNAE 3-SAT

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Related Items

Relating planar graph drawings to planar satisfiability problems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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
• On strong NP-completeness of rational problems
• Basic graph theory
• Efficient Algorithms for Petersen's Matching Theorem
• On the Hardness of Point-Set Embeddability
• Maximum Cardinality Simple 2-matchings in Subcubic Graphs
• A new proof of 3-colorability of Eulerian triangulations
• Planar Formulae and Their Uses
• The Planar Hamiltonian Circuit Problem is NP-Complete
• On Area-Optimal Planar Graph Drawings
• Unifying maximum cut and minimum cut of a planar graph
• The complexity of satisfiability problems
• The complexity of theorem-proving procedures
• How to Draw a Graph
• Hard tiling problems with simple tiles