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

2016/04/19 by Andreas Darmann, Darmann, Andreas, Janosch Döcker +3 · 1 citation
Computer Science · Engineering · #Computational Complexity (cs.CC) #Computational Geometry and Mesh Generation #FOS: Computer and information sciences #Optimization and Packing Problems #Vehicle Routing Optimization Methods

paper · pdf · doi:10.48550/arxiv.1604.05588

openalex publication_date 2016/04/19 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

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

Cited by

• Spanning Trees with a Small Vertex Cover: the Complexity on Specific Graph Classes

Related

• The Complexity of Planar Counting Problems
• Positive Planar Satisfiability Problems under 3-Connectivity Constraints
• Testing Gap k-planarity is NP-complete
• On a variant of Monotone NAE-3SAT and the Triangle-Free Cut problem
• Constrained and Ordered Level Planarity Parameterized by the Number of Levels