Recognizing string graphs in NP
From MaRDI portal
Publication:5917583
DOI10.1016/S0022-0000(03)00045-XzbMath1072.68081OpenAlexW4213071722MaRDI QIDQ5917583
Daniel Štefanković, Marcus Schaefer, Eric Sedgwick
Publication date: 18 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/s0022-0000(03)00045-x
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items (42)
CPG graphs: some structural and hardness results ⋮ Spatial reasoning in a fuzzy region connection calculus ⋮ Drawing interactive Euler diagrams from region connection calculus specifications ⋮ Untangling two systems of noncrossing curves ⋮ Hanani--Tutte and Hierarchical Partial Planarity ⋮ Finding geometric representations of apex graphs is NP-hard ⋮ Drawing Euler Diagrams from Region Connection Calculus Specifications with Local Search ⋮ Improved enumeration of simple topological graphs ⋮ Intersection Graphs of Rays and Grounded Segments ⋮ Almost all string graphs are intersection graphs of plane convex sets ⋮ Folding and Spiralling: The Word View ⋮ \(B_0\)-VPG representation of AT-free outerplanar graphs ⋮ Recognition of Polygon-Circle Graphs and Graphs of Interval Filaments Is NP-Complete ⋮ B0-VPG Representation of AT-free Outerplanar Graphs ⋮ Simple realizability of complete abstract topological graphs in P ⋮ 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 ⋮ An algorithm for the maximum weight independent set problem on outerstring graphs ⋮ Well quasi orders in subclasses of bounded treewidth graphs and their algorithmic applications ⋮ Crossing numbers of graphs with rotation systems ⋮ Spiraling and folding: the word view ⋮ Optimality program in segment and string graphs ⋮ General lower bounds for the minor crossing number of graphs ⋮ The Complexity of Several Realizability Problems for Abstract Topological Graphs ⋮ Unnamed Item ⋮ Subexponential algorithms for variants of the homomorphism problem in string graphs ⋮ WORD EQUATIONS WITH ONE UNKNOWN ⋮ Tracing compressed curves in triangulated surfaces ⋮ Word Equations with One Unknown ⋮ Maximum Independent Set in 2-Direction Outersegment Graphs ⋮ 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 ⋮ Planarity of streamed graphs ⋮ Segment representations with small resolution ⋮ 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. II: Recognizing string graphs is NP-hard
- String graphs. I: The number of critical nonstring graphs is infinite
- String graphs requiring exponential representations
- Which crossing number is it anyway?
- Crossing Number is NP-Complete
- Solving trace equations using lexicographical normal forms
- Efficient algorithms for Lempel-Ziv encoding
- Decidability of string graphs
- Topology of Thin Film RC Circuits
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: Recognizing string graphs in NP
