Decidability of string graphs

DOI10.1016/J.JCSS.2003.07.002zbMATH Open1073.68065OpenAlexW3030259189MaRDI QIDQ1887714

Marcus Schaefer, D. Š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)

Cites Work

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

Cited In (26)

• Separators in region intersection graphs
• String graphs and incomparability graphs
• Bad drawings of small complete graphs
• Computing the Fréchet Distance Between Polygons with Holes
• Spiraling and folding: the word view
• Efficient enumeration of drawings and combinatorial structures for maximal planar graphs
• String graphs and incomparability graphs
• Hanani--Tutte and Hierarchical Partial Planarity
• Title not available (Why is that?)
• Diamond Subgraphs in the Reduction Graph of a One-Rule String Rewriting System
• Treewidth versus Clique Number. I. Graph Classes with a Forbidden Structure
• Folding and Spiralling: The Word View
• General lower bounds for the minor crossing number of graphs
• Clustered coloring of graphs with bounded layered treewidth and bounded degree
• Outerstring Graphs are $\chi$-Bounded
• Spatial reasoning with \(\mathcal{RCC} 8\) and connectedness constraints in Euclidean spaces
• Well quasi orders in subclasses of bounded treewidth graphs and their algorithmic applications
• String graphs. II: Recognizing string graphs is NP-hard
• The Complexity of Several Realizability Problems for Abstract Topological Graphs
• Orthogonal Tree Decompositions of Graphs
• Almost all string graphs are intersection graphs of plane convex sets
• Note on the pair-crossing number and the odd-crossing number
• Simple realizability of complete abstract topological graphs in P
• Refining the hierarchies of classes of geometric intersection graphs
• Almost all string graphs are intersection graphs of plane convex sets
• Blocks of Hypergraphs

Recommendations

• Title not available (Why is that?) 👍 👎
• Title not available (Why is that?) 👍 👎
• Title not available (Why is that?) 👍 👎
• Recognizing string graphs in NP 👍 👎
• String graphs and incomparability graphs 👍 👎
• Recognizing string graphs is decidable 👍 👎
• String graphs and incomparability graphs 👍 👎
• Decidability of string graphs 👍 👎
• Constructing decidable graphs from decidable structures 👍 👎
• String decompositions of graphs 👍 👎

This page was built for publication: Decidability of string graphs

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