scientific article; zbMATH DE number 7238965
From MaRDI portal
Publication:5116474
DOI10.4230/LIPIcs.SWAT.2018.10zbMath1477.68200MaRDI QIDQ5116474
Ahmad Biniaz, Martin Derka, Therese C. Biedl
Publication date: 25 August 2020
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph representations (geometric and intersection representations, etc.) (05C62)
Related Items (2)
Finding geometric representations of apex graphs is \textsf{NP}-hard ⋮ Outerstring Graphs are $\chi$-Bounded
Cites Work
- Unnamed Item
- Coloring intersection graphs of \(x\)-monotone curves in the plane
- An algorithm for the maximum weight independent set problem on outerstring graphs
- Weakly transitive orientations, Hasse diagrams and string graphs
- Separator theorems and Turán-type results for planar intersection graphs
- String graphs. II: Recognizing string graphs is NP-hard
- String graphs requiring exponential representations
- The max clique problem in classes of string-graphs
- Intersection graphs of curves in the plane
- Intersection graphs of rays and grounded segments
- The Hamiltonian circuit problem for circle graphs is NP-complete
- Recognizing string graphs is decidable
- Independent set of intersection graphs of convex objects in 2D
- A Separator Theorem for String Graphs and its Applications
- Approximation Algorithms for Polynomial-Expansion and Low-Density Graphs
- The Complexity of Coloring Circular Arcs and Chords
- The Rectilinear Steiner Tree Problem is $NP$-Complete
- Separators in region intersection graphs
- Every planar graph is the intersection graph of segments in the plane
- Decidability of string graphs
- Topology of Thin Film RC Circuits
- Recognizing string graphs in NP
- Refining the hierarchies of classes of geometric intersection graphs
This page was built for publication:
