Recognizing string graphs is decidable

DOI10.1007/s00454-002-2891-4zbMath1050.68111OpenAlexW1518473637MaRDI QIDQ1864118

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)

Related Items (16)

Tree densities in sparse graph classes ⋮ Folding and Spiralling: The Word View ⋮ Graph product structure for non-minor-closed classes ⋮ Simple realizability of complete abstract topological graphs in P ⋮ String graphs and incomparability graphs ⋮ Orthogonal Tree Decompositions of Graphs ⋮ Well quasi orders in subclasses of bounded treewidth graphs and their algorithmic applications ⋮ Spiraling and folding: the word view ⋮ Conflict-free coloring of string graphs ⋮ General lower bounds for the minor crossing number of graphs ⋮ The Complexity of Several Realizability Problems for Abstract Topological Graphs ⋮ Unnamed Item ⋮ Tracing compressed curves in triangulated surfaces ⋮ Notes on graph product structure theory ⋮ Maximum Independent Set in 2-Direction Outersegment Graphs ⋮ Outerstring Graphs are $\chi$-Bounded

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