Planar 3-SAT with a clause/variable cycle

DOI10.4230/LIPIcs.SWAT.2018.31zbMath1477.68294OpenAlexW2949221776MaRDI QIDQ5116495

Alexander Pilz

Publication date: 25 August 2020

Full work available at URL: http://drops.dagstuhl.de/opus/volltexte/2018/8857/pdf/LIPIcs-SWAT-2018-31.pdf

zbMATH Keywords

planar graph3-SAT1-in-3-SAT

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Planar graphs; geometric and topological aspects of graph theory (05C10) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Eulerian and Hamiltonian graphs (05C45)

Related Items

Games, Puzzles and Treewidth, Vertex-to-point conflict-free chromatic guarding is NP-hard, On the hull number on cycle convexity of graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Nested satisfiability
• A simplified NP-complete satisfiability problem
• How to draw a planar graph on a grid
• Flip distance between triangulations of a simple polygon is NP-complete
• A partial k-arboretum of graphs with bounded treewidth
• Satisfiability of co-nested formulas
• The complexity of induced minors and related problems
• A left-first search algorithm for planar graphs
• Classic Nintendo games are (computationally) hard
• Counting truth assignments of formulas of bounded tree-width or clique-width
• The Complexity of Counting in Sparse, Regular, and Planar Graphs
• Noncrossing Subgraphs in Topological Layouts
• Minimum-weight triangulation is NP-hard
• Planar Formulae and Their Uses
• Determining the thickness of graphs is NP-hard
• The Problem of Compatible Representatives
• The Complexity of Planar Counting Problems
• On Representatives of Subsets
• OPTIMAL BINARY SPACE PARTITIONS FOR SEGMENTS IN THE PLANE
• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs