Pages that link to "Item:Q1112845"
From MaRDI portal
The following pages link to String graphs. II: Recognizing string graphs is NP-hard (Q1112845):
Displaying 50 items.
- Spatial reasoning with \(\mathcal{RCC} 8\) and connectedness constraints in Euclidean spaces (Q464617) (← links)
- Simple realizability of complete abstract topological graphs in P (Q633211) (← links)
- An algorithm for the maximum weight independent set problem on outerstring graphs (Q680149) (← links)
- CPG graphs: some structural and hardness results (Q827595) (← links)
- Spatial reasoning in a fuzzy region connection calculus (Q835806) (← links)
- A branch-and-cut approach to the crossing number problem (Q951113) (← links)
- String graphs. I: The number of critical nonstring graphs is infinite (Q1121917) (← links)
- String graphs requiring exponential representations (Q1121918) (← links)
- Thresholds for classes of intersection graphs (Q1201264) (← links)
- Classes and recognition of curve contact graphs (Q1272471) (← links)
- Topological queries in spatial databases (Q1305920) (← links)
- A special planar satisfiability problem and a consequence of its NP- completeness (Q1331895) (← links)
- On intersection representations of co-planar graphs (Q1377831) (← links)
- The maximal clique and colourability of curve contact graphs (Q1382253) (← links)
- Cops and robbers on intersection graphs (Q1645059) (← links)
- Two-layer drawings of bipartite graphs (Q1689940) (← links)
- Well quasi orders in subclasses of bounded treewidth graphs and their algorithmic applications (Q1759678) (← links)
- Decidability of string graphs (Q1887714) (← links)
- Subexponential-time algorithms for finding large induced sparse subgraphs (Q2041989) (← links)
- Characterization of \(\mathrm{B}_0\)-VPG cocomparability graphs and a 2D visualization of their posets (Q2088073) (← links)
- On dominating set of some subclasses of string graphs (Q2144448) (← links)
- Finding geometric representations of apex graphs is NP-hard (Q2154093) (← links)
- Almost all string graphs are intersection graphs of plane convex sets (Q2189736) (← links)
- Simple realizability of complete abstract topological graphs simplified (Q2189738) (← links)
- Subexponential algorithms for variants of the homomorphism problem in string graphs (Q2301363) (← links)
- Bounds on the bend number of split and cocomparability graphs (Q2322713) (← links)
- Planarity of streamed graphs (Q2333805) (← links)
- Segment representations with small resolution (Q2338214) (← links)
- Crossing-constrained hierarchical drawings (Q2458930) (← links)
- Distinguishing graphs via cycles (Q2695304) (← links)
- 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> (Q2851437) (← links)
- Order-Preserving 1-String Representations of Planar Graphs (Q2971141) (← links)
- Maximum Independent Set in 2-Direction Outersegment Graphs (Q3104773) (← links)
- Recognizing Some Subclasses of Vertex Intersection Graphs of 0-Bend Paths in a Grid (Q3104787) (← links)
- Recognition of Polygon-Circle Graphs and Graphs of Interval Filaments Is NP-Complete (Q3508571) (← links)
- A New Approach to Exact Crossing Minimization (Q3541091) (← links)
- Intersection Graphs of Rays and Grounded Segments (Q4585058) (← links)
- Orthogonal Tree Decompositions of Graphs (Q4634649) (← links)
- Separators in region intersection graphs (Q4638049) (← links)
- Characterization and a 2D Visualization of B$$_{0}$$-VPG Cocomparability Graphs (Q5014117) (← links)
- Hanani--Tutte and Hierarchical Partial Planarity (Q5058130) (← links)
- (Q5116474) (← links)
- Almost all string graphs are intersection graphs of plane convex sets (Q5116528) (← links)
- Maximum Cut Parameterized by Crossing Number (Q5119374) (← links)
- Outerstring Graphs are $\chi$-Bounded (Q5244121) (← links)
- The Complexity of Several Realizability Problems for Abstract Topological Graphs (Q5452218) (← links)
- Efficient Local Representations of Graphs (Q5506777) (← links)
- String graphs and incomparability graphs (Q5891657) (← links)
- Refining the hierarchies of classes of geometric intersection graphs (Q5892293) (← links)
- Recognizing string graphs in NP (Q5917583) (← links)
