Decidability of string graphs

DOI10.1016/j.jcss.2003.07.002zbMath1073.68065OpenAlexW3030259189MaRDI QIDQ1887714

Marcus Schaefer, Daniel Štefanković

Publication date: 22 November 2004

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jcss.2003.07.002

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Related Items (20)

Bad drawings of small complete graphs ⋮ Computing the Fréchet Distance Between Polygons with Holes ⋮ Hanani--Tutte and Hierarchical Partial Planarity ⋮ Almost all string graphs are intersection graphs of plane convex sets ⋮ Folding and Spiralling: The Word View ⋮ Simple realizability of complete abstract topological graphs in P ⋮ String graphs and incomparability graphs ⋮ Spatial reasoning with \(\mathcal{RCC} 8\) and connectedness constraints in Euclidean spaces ⋮ Refining the hierarchies of classes of geometric intersection graphs ⋮ Orthogonal Tree Decompositions of Graphs ⋮ Blocks of Hypergraphs ⋮ Note on the pair-crossing number and the odd-crossing number ⋮ Well quasi orders in subclasses of bounded treewidth graphs and their algorithmic applications ⋮ Spiraling and folding: the word view ⋮ General lower bounds for the minor crossing number of graphs ⋮ The Complexity of Several Realizability Problems for Abstract Topological Graphs ⋮ Separators in region intersection graphs ⋮ Outerstring Graphs are $\chi$-Bounded ⋮ Treewidth versus Clique Number. I. Graph Classes with a Forbidden Structure ⋮ Almost all string graphs are intersection graphs of plane convex sets

Cites Work

• Maintaining knowledge about temporal intervals
• How to draw a planar graph on a grid
• String graphs. II: Recognizing string graphs is NP-hard
• String graphs. I: The number of critical nonstring graphs is infinite
• String graphs requiring exponential representations
• Intersection graphs of curves in the plane
• Topological queries in spatial databases
• Classical recursion theory. Vol. II
• Which crossing number is it anyway?
• Crossing Number is NP-Complete
• Computing crossing numbers in quadratic time
• Topology of Thin Film RC Circuits
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Decidability of string graphs