String graphs. II: Recognizing string graphs is NP-hard

Cites Work

Title not available (Why is that?)
Title not available (Why is that?)
Title not available (Why is that?)
Graph minors. XIII: The disjoint paths problem
Intersection graphs of curves in the plane
Topology of Thin Film RC Circuits
Energy, central charge, and the BPS bound for $1+1$-dimensional supersymmetric solitons
String graphs. I: The number of critical nonstring graphs is infinite
Determining the thickness of graphs is NP-hard
Graph minors. XVIII: Tree-decompositions and well-quasi-ordering

Cited In (63)

Proper colorability of segment intersection graphs
Computing list homomorphisms in geometric intersection graphs
Clustered coloring of graphs with bounded layered treewidth and bounded degree
On unit grid intersection graphs and several other intersection graph classes
Proper colorability of segment intersection graphs
B0-VPG Representation of AT-free Outerplanar Graphs
$B_0$-VPG representation of AT-free outerplanar graphs
Graphs of intersections of closed polygonal chains
Separators in region intersection graphs
A branch-and-cut approach to the crossing number problem
Bounds on the bend number of split and cocomparability graphs
Finding geometric representations of apex graphs is NP-hard
Topological queries in spatial databases
CPG graphs: some structural and hardness results
A New Approach to Exact Crossing Minimization
String graphs. I: The number of critical nonstring graphs is infinite
Two-layer drawings of bipartite graphs
Segment representations with small resolution
String graphs and incomparability graphs
Hanani--Tutte and Hierarchical Partial Planarity
Maximum Cut Parameterized by Crossing Number
Title not available (Why is that?)
Optimality program in segment and string graphs
Distinguishing graphs via cycles
Intersection Graphs of Rays and Grounded Segments
Order-Preserving 1-String Representations of Planar Graphs
Subexponential algorithms for variants of the homomorphism problem in string graphs
On dominating set of some subclasses of string graphs
General lower bounds for the minor crossing number of graphs
$D$-collapsibility is NP-complete for $d \geq 4$
On intersection representations of co-planar graphs
Characterization and a 2D Visualization of B$$_{0}$$-VPG Cocomparability Graphs
Outerstring Graphs are $\chi$-Bounded
Crossing patterns of segments
Efficient Local Representations of Graphs
Spatial reasoning with $\mathcal{RCC} 8$ and connectedness constraints in Euclidean spaces
Classes and recognition of curve contact graphs
The maximal clique and colourability of curve contact graphs
A special planar satisfiability problem and a consequence of its NP- completeness
Thresholds for classes of intersection graphs
Subexponential-time algorithms for finding large induced sparse subgraphs
Maximum Independent Set in 2-Direction Outersegment Graphs
Cops and robbers on intersection graphs
Well quasi orders in subclasses of bounded treewidth graphs and their algorithmic applications
String graphs requiring exponential representations
The Complexity of Several Realizability Problems for Abstract Topological Graphs
Recognizing Some Subclasses of Vertex Intersection Graphs of 0-Bend Paths in a Grid
Orthogonal Tree Decompositions of Graphs
Almost all string graphs are intersection graphs of plane convex sets
Decidability of string graphs
Finding geometric representations of apex graphs is \textsf{NP}-hard
Spatial reasoning in a fuzzy region connection calculus
Simple realizability of complete abstract topological graphs simplified
Topology of strings: median string is NP-complete
Recognition of Polygon-Circle Graphs and Graphs of Interval Filaments Is NP-Complete
Characterization of $\mathrm{B}_0$-VPG cocomparability graphs and a 2D visualization of their posets
Simple realizability of complete abstract topological graphs in P
Refining the hierarchies of classes of geometric intersection graphs
Planarity of streamed graphs
Crossing-constrained hierarchical drawings
Recognizing string graphs in NP
Almost all string graphs are intersection graphs of plane convex sets
An algorithm for the maximum weight independent set problem on outerstring graphs

Recommendations

This page was built for publication: String graphs. II: Recognizing string graphs is NP-hard

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