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

DOI10.1016/0166-218X(94)90143-0zbMath0810.68083OpenAlexW2085486788WikidataQ127571235 ScholiaQ127571235MaRDI QIDQ1331895

Publication date: 27 September 1994

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0166-218x(94)90143-0

zbMATH Keywords

intersection graphs NP-complete satisfiability

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Related Items

On finding short resolution refutations and small unsatisfiable subsets ⋮ CPG graphs: some structural and hardness results ⋮ Uniformity of Point Samples in Metric Spaces Using Gap Ratio ⋮ Twin-Cover: Beyond Vertex Cover in Parameterized Algorithmics ⋮ Structural parameterizations for boxicity ⋮ It is tough to be a plumber ⋮ Separation dimension of graphs and hypergraphs ⋮ Boxicity of graphs on surfaces ⋮ Positive planar satisfiability problems under 3-connectivity constraints ⋮ Permuting matrices to avoid forbidden submatrices ⋮ Geometric representation of graphs in low dimension using axis parallel boxes ⋮ Chronological rectangle digraphs ⋮ Boxicity and treewidth ⋮ Finding geometric representations of apex graphs is NP-hard ⋮ Ferrers dimension of grid intersection graphs ⋮ On orthogonal ray graphs ⋮ The hardness of approximating the boxicity, cubicity and threshold dimension of a graph ⋮ Complexity of domination in triangulated plane graphs ⋮ Domination chain: characterisation, classical complexity, parameterised complexity and approximability ⋮ Chronological rectangle digraphs which are two-terminal series-parallel ⋮ Local boxicity and maximum degree ⋮ Bounding threshold dimension: realizing graphic Boolean functions as the AND of majority gates ⋮ Extension of some edge graph problems: standard, parameterized and approximation complexity ⋮ On the Cubicity of Interval Graphs ⋮ Co-bipartite neighborhood edge elimination orderings ⋮ Boxicity of line graphs ⋮ The Complexity of the Partial Order Dimension Problem: Closing the Gap ⋮ Relating planar graph drawings to planar satisfiability problems ⋮ Sublinear approximation algorithms for boxicity and related problems ⋮ On Local Structures of Cubicity 2 Graphs ⋮ On spanning galaxies in digraphs ⋮ Separability, boxicity, and partial orders ⋮ Reasoning about visibility ⋮ Proper colorability of segment intersection graphs ⋮ Hardness of uncertain segment cover, contiguous SAT and visibility with uncertain obstacles ⋮ Finding geometric representations of apex graphs is \textsf{NP}-hard ⋮ Spanners of bounded degree graphs ⋮ Recognizing geometric intersection graphs stabbed by a line ⋮ Simple realizability of complete abstract topological graphs in P ⋮ On the complexity of recognizing Stick, BipHook and max point-tolerance graphs ⋮ On orthogonal ray trees ⋮ The many facets of upper domination ⋮ Stick graphs with length constraints ⋮ Local and union boxicity ⋮ Paths of bounded length and their cuts: parameterized complexity and algorithms ⋮ Strong edge-colouring and induced matchings ⋮ Boundary properties of the satisfiability problems ⋮ On simplified NP-complete variants of \textsc{Monotone} 3\textsc{-Sat} ⋮ Boxicity of circular arc graphs ⋮ Relationships between the class of unit grid intersection graphs and other classes of bipartite graphs ⋮ On stable cutsets in claw-free graphs and planar graphs ⋮ The complexity of partitioning into disjoint cliques and a triangle-free graph ⋮ Optimal grid representations ⋮ Oriented, 2-edge-colored, and 2-vertex-colored homomorphisms ⋮ Boxicity and maximum degree ⋮ Parameterized complexity of the spanning tree congestion problem ⋮ Dimension-2 poset competition numbers and dimension-2 poset double competition numbers ⋮ Boxicity and cubicity of asteroidal triple free graphs ⋮ Systems of distant representatives ⋮ On the cubicity of bipartite graphs ⋮ Recognition and drawing of stick graphs ⋮ Grid intersection graphs and order dimension ⋮ Boxicity of series-parallel graphs ⋮ Cubicity, degeneracy, and crossing number ⋮ The cubicity of hypercube graphs ⋮ The Complexity of Several Realizability Problems for Abstract Topological Graphs ⋮ The Monotone Satisfiability Problem with Bounded Variable Appearances ⋮ A constant factor approximation algorithm for boxicity of circular arc graphs ⋮ Characterizations of cographs as intersection graphs of paths on a grid ⋮ On rectangle intersection graphs with stab number at most two ⋮ Upper Domination: Complexity and Approximation ⋮ Boxicity of graphs with bounded degree ⋮ Cubicity, boxicity, and vertex cover ⋮ An upper bound for cubicity in terms of boxicity ⋮ Boxicity of Halin graphs ⋮ On the complexity of solution extension of optimization problems ⋮ String graphs of k-bend paths on a grid ⋮ On the stab number of rectangle intersection graphs ⋮ On the cubicity of certain graphs ⋮ On the cubicity of interval graphs ⋮ The capture time of a graph ⋮ Spanning galaxies in digraphs ⋮ Cubicity of Interval Graphs and the Claw Number ⋮ Segment representations with small resolution ⋮ Face covers and the genus problem for apex graphs ⋮ Lower bounds for boxicity ⋮ On-line coloring of geometric intersection graphs

Cites Work