Linear Planar 3-SAT and Its Applications in Planning

Victorien Desbois, Ocan Sankur, François Schwarzentruber

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 li…