Positive Planar Satisfiability Problems under 3-Connectivity Constraints

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

A 3-SAT problem is called positive and planar if all the literals are positive and the clause-variable incidence graph (i.e., SAT graph) is planar. The NAE 3-SAT and 1-in-3-SAT are…