Determining the thickness of graphs is NP-hard
From MaRDI portal
Publication:3969882
DOI10.1017/S030500410006028XzbMath0503.68048OpenAlexW2047095042WikidataQ56689316 ScholiaQ56689316MaRDI QIDQ3969882
Publication date: 1983
Published in: Mathematical Proceedings of the Cambridge Philosophical Society (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1017/s030500410006028x
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)
Related Items
A special planar satisfiability problem and a consequence of its NP- completeness ⋮ The thickness of amalgamations and Cartesian product of graphs ⋮ Regular codes in regular graphs are difficult ⋮ It is tough to be a plumber ⋮ Thickness of the subgroup intersection graph of a finite group ⋮ Rectangle-visibility representations of bipartite graphs ⋮ String graphs. II: Recognizing string graphs is NP-hard ⋮ Angle Covers: Algorithms and Complexity ⋮ The thickness of a minor-excluded class of graphs ⋮ The thickness of the complete multipartite graphs and the join of graphs ⋮ Complexity of domination in triangulated plane graphs ⋮ A tribute to Frank Harary (in honor of his 70th birthday) ⋮ On the complexity of restoring corrupted colorings ⋮ The thickness of fan-planar graphs is at most three ⋮ Note on \(k\)-planar crossing numbers ⋮ Multilayer grid embeddings for VLSI ⋮ A successful concept for measuring non-planarity of graphs: The crossing number. ⋮ Boundary properties of the satisfiability problems ⋮ Thickness and outerthickness for embedded graphs ⋮ Thickness and colorability of geometric graphs ⋮ A note on Halton's conjecture ⋮ Recovery of disrupted airline operations using \(k\)-maximum matching in graphs ⋮ Biplanar crossing numbers. II. Comparing crossing numbers and biplanar crossing numbers using the probabilistic method ⋮ The 6-girth-thickness of the complete graph ⋮ Worst case analysis of a greedy algorithm for graph thickness ⋮ Non-planar core reduction of graphs ⋮ On finding a biconnected spanning planar subgraph with applications to the facilities layout problem ⋮ Thickness-two graphs. II: More new nine-critical graphs, independence ratio, cloned planar graphs, and singly and doubly outerplanar graphs ⋮ Planar 3-SAT with a clause/variable cycle ⋮ A simulated annealing algorithm for determining the thickness of a graph ⋮ The 4-girth-thickness of the complete multipartite graph ⋮ A genetic algorithm for determining the thickness of a graph ⋮ Remarks on the thickness and outerthickness of a graph
Cites Work
