Recognizing string graphs is decidable

DOI10.1007/S00454-002-2891-4MaRDI QIDQ1864118zbMATH OpenOpenAlexFDO

Authors János Pach, Géza Tóth

Publication date 17 March 2003

Published in Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00454-002-2891-4

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• scientific article; zbMATH DE number 2084281
• Recognizing string graphs in NP
• String graphs. II: Recognizing string graphs is NP-hard
• Decidability of string graphs
• Decidability of string graphs

Cited in

(22)

• scientific article; zbMATH DE number 2084281 (Why is no real title available?)
• Spiraling and folding: the word view
• Tracing compressed curves in triangulated surfaces
• String graphs and incomparability graphs
• Orthogonal tree decompositions of graphs
• Maximum independent set in 2-direction outersegment graphs
• Graph product structure for non-minor-closed classes
• Conflict-free coloring of string graphs
• Folding and Spiralling: The Word View
• Decidability of string graphs
• Tree densities in sparse graph classes
• General lower bounds for the minor crossing number of graphs
• Clustered coloring of graphs with bounded layered treewidth and bounded degree
• Well quasi orders in subclasses of bounded treewidth graphs and their algorithmic applications
• String graphs. II: Recognizing string graphs is NP-hard
• String graphs requiring exponential representations
• On the size of outer-string representations
• The Complexity of Several Realizability Problems for Abstract Topological Graphs
• Decidability of string graphs
• Notes on graph product structure theory
• Outerstring graphs are \(\chi \)-bounded
• Simple realizability of complete abstract topological graphs in P

This page was built for publication: Recognizing string graphs is decidable

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