On planar variants of the monotone satisfiability problem with bounded variable appearances

We show NP-completeness for several planar variants of the monotone satisfiability problem with bounded variable appearances. With one exception the presented variants have an associated bipartite graph where the vertex degree is bounded by at most four. Hence, a planar and orthogonal drawing for these graphs can be computed efficiently, which may turn out to be useful in reductions using these variants as a starting point for proving some decision problem to be NP-hard.