scientific article

zbMath0697.05052MaRDI QIDQ3474685

Jan Kratochvíl, Ji{ří} Matoušek

Publication date: 1989

Full work available at URL: https://eudml.org/doc/17790

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

intersection graphNP-hard problemstring graph

Mathematics Subject Classification ID

Graph theory (05C99)

Related Items

A special planar satisfiability problem and a consequence of its NP- completeness ⋮ Finding geometric representations of apex graphs is NP-hard ⋮ Simple realizability of complete abstract topological graphs simplified ⋮ Topological Drawings of Complete Bipartite Graphs ⋮ Finding geometric representations of apex graphs is \textsf{NP}-hard ⋮ Simple realizability of complete abstract topological graphs in P ⋮ On orthogonal ray trees ⋮ Complexity of Geometric k-Planarity for Fixed k ⋮ A Separator Theorem for String Graphs and Its Applications ⋮ d-collapsibility is NP-complete for <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" altimg="si1.gif" overflow="scroll"><mml:mi>d</mml:mi><mml:mo>⩾</mml:mo><mml:mn>4</mml:mn></mml:math> ⋮ On the Complexity of Some Geometric Problems With Fixed Parameters