A special planar satisfiability problem and a consequence of its NP-completeness

1994/08/01 by Jan Kratochvíl, Jan Kratochvı́l · 6 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics #Completeness (order theory) #Computational Geometry and Mesh Generation #Discrete mathematics #Graph #Graph Theory and Algorithms #Intersection (aeronautics) #Mathematics #NP-complete #Planar graph #Satisfiability #Time complexity

paper · doi:10.1016/0166-218x(94)90143-0

crossref issued 1994/08/01 · crossref published 1994/08/01 · crossref published-print 1994/08/01 · openalex publication_date 1994/08/01 · crossref created 2002/07/26 · crossref deposited 2019/04/13 · openalex created_date 2025/10/10 · crossref indexed 2026/06/16 · openalex updated_date 2026/08/03

Citations

• Grid intersection graphs and boxicity
• The Complexity of the Partial Order Dimension Problem
• Intersection graphs of curves in the plane
• On grid intersection graphs

Cited by

• Boxicity and treewidth
• Parameterized Algorithms for Boxicity
• Geometric Representation of Graphs in Low Dimension Using Axis Parallel Boxes
• Cubicity, degeneracy, and crossing number
• Boxicity and Poset Dimension
• Boxicity [wikipedia]