scientific article; zbMATH DE number 4142090

zbMATH Open0697.05052MaRDI QIDQ3474685FDOQ3474685

Authors: Jan Kratochvíl, Jiří Matoušek 

Publication date: 1989

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

Title of this publication is not available (Why is that?)

Recommendations

• String graphs. II: Recognizing string graphs is NP-hard
• Recognizing string graphs in NP
• String graphs. I: The number of critical nonstring graphs is infinite
• The max clique problem in classes of string-graphs
• scientific article; zbMATH DE number 3981198

zbMATH Keywords

intersection graphNP-hard problemstring graph

Mathematics Subject Classification ID

Graph theory (05C99)

Cited In (19)

• Finding geometric representations of apex graphs is NP-hard
• String graphs. I: The number of critical nonstring graphs is infinite
• Complexity of geometric \(k\)-planarity for fixed \(k\)
• On the intractability landscape of digraph intersection representations
• The max clique problem in classes of string-graphs
• \(D\)-collapsibility is NP-complete for \(d \geq 4\)
• Approximation hardness of optimization problems in intersection graphs of \(d\)-dimensional boxes
• A special planar satisfiability problem and a consequence of its NP- completeness
• Topological Drawings of Complete Bipartite Graphs
• On the complexity of some geometric problems with fixed parameters
• Complexity of some geometric and topological problems
• On orthogonal ray trees
• Complexity of circuit intersection in graphs
• Finding geometric representations of apex graphs is \textsf{NP}-hard
• A Separator Theorem for String Graphs and Its Applications
• Simple realizability of complete abstract topological graphs simplified
• Contact graphs of line segments are NP-complete
• Simple realizability of complete abstract topological graphs in P
• Recognizing string graphs in NP

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3474685)