String graphs. II: Recognizing string graphs is NP-hard
From MaRDI portal
Publication:1112845
DOI10.1016/0095-8956(91)90091-WzbMath0661.05054MaRDI QIDQ1112845
Publication date: 1991
Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)
Graph theory (including graph drawing) in computer science (68R10) Structural characterization of families of graphs (05C75)
Related Items
A special planar satisfiability problem and a consequence of its NP- completeness ⋮ CPG graphs: some structural and hardness results ⋮ Spatial reasoning in a fuzzy region connection calculus ⋮ Decidability of string graphs ⋮ On dominating set of some subclasses of string graphs ⋮ Hanani--Tutte and Hierarchical Partial Planarity ⋮ Cops and robbers on intersection graphs ⋮ Finding geometric representations of apex graphs is NP-hard ⋮ On intersection representations of co-planar graphs ⋮ String graphs. I: The number of critical nonstring graphs is infinite ⋮ String graphs requiring exponential representations ⋮ The maximal clique and colourability of curve contact graphs ⋮ Intersection Graphs of Rays and Grounded Segments ⋮ Computing list homomorphisms in geometric intersection graphs ⋮ Almost all string graphs are intersection graphs of plane convex sets ⋮ Simple realizability of complete abstract topological graphs simplified ⋮ Two-layer drawings of bipartite graphs ⋮ \(B_0\)-VPG representation of AT-free outerplanar graphs ⋮ Recognition of Polygon-Circle Graphs and Graphs of Interval Filaments Is NP-Complete ⋮ Proper colorability of segment intersection graphs ⋮ Finding geometric representations of apex graphs is \textsf{NP}-hard ⋮ B0-VPG Representation of AT-free Outerplanar Graphs ⋮ Simple realizability of complete abstract topological graphs in P ⋮ Distinguishing graphs via cycles ⋮ Maximum Cut Parameterized by Crossing Number ⋮ Order-Preserving 1-String Representations of Planar Graphs ⋮ 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 ⋮ A New Approach to Exact Crossing Minimization ⋮ Orthogonal Tree Decompositions of Graphs ⋮ Crossing-constrained hierarchical drawings ⋮ An algorithm for the maximum weight independent set problem on outerstring graphs ⋮ A branch-and-cut approach to the crossing number problem ⋮ Thresholds for classes of intersection graphs ⋮ Well quasi orders in subclasses of bounded treewidth graphs and their algorithmic applications ⋮ Crossing patterns of segments ⋮ Optimality program in segment and string graphs ⋮ Recognizing string graphs in NP ⋮ General lower bounds for the minor crossing number of graphs ⋮ The Complexity of Several Realizability Problems for Abstract Topological Graphs ⋮ Subexponential-time algorithms for finding large induced sparse subgraphs ⋮ Unnamed Item ⋮ Subexponential algorithms for variants of the homomorphism problem in string graphs ⋮ Classes and recognition of curve contact graphs ⋮ Maximum Independent Set in 2-Direction Outersegment Graphs ⋮ Recognizing Some Subclasses of Vertex Intersection Graphs of 0-Bend Paths in a Grid ⋮ Separators in region intersection graphs ⋮ Bounds on the bend number of split and cocomparability graphs ⋮ Outerstring Graphs are $\chi$-Bounded ⋮ Characterization of \(\mathrm{B}_0\)-VPG cocomparability graphs and a 2D visualization of their posets ⋮ d-collapsibility is NP-complete for <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" altimg="si1.gif" overflow="scroll"><mml:mi>d</mml:mi><mml:mo>⩾</mml:mo><mml:mn>4</mml:mn></mml:math> ⋮ Planarity of streamed graphs ⋮ Efficient Local Representations of Graphs ⋮ Segment representations with small resolution ⋮ Topological queries in spatial databases ⋮ Characterization and a 2D Visualization of B$$_{0}$$-VPG Cocomparability Graphs ⋮ Almost all string graphs are intersection graphs of plane convex sets
Cites Work
- String graphs. I: The number of critical nonstring graphs is infinite
- Intersection graphs of curves in the plane
- Graph minors. XVIII: Tree-decompositions and well-quasi-ordering
- Energy, central charge, and the BPS bound for \(1+1\)-dimensional supersymmetric solitons
- Graph minors. XIII: The disjoint paths problem
- Determining the thickness of graphs is NP-hard
- Topology of Thin Film RC Circuits
- Unnamed Item
- Unnamed Item
- Unnamed Item
