On the size of outer-string representations

DOI10.4230/LIPICS.SWAT.2018.10zbMATH Open1477.68200MaRDI QIDQ5116474FDOQ5116474

Authors: Ahmad Biniaz, Martin Derka, Therese Biedl 

Publication date: 25 August 2020

Recommendations

• Computing maximum independent set on outerstring graphs and their relatives
• An algorithm for the maximum weight independent set problem on outerstring graphs
• Maximum independent set in 2-direction outersegment graphs
• String graphs requiring exponential representations
• Outerstring graphs are \(\chi\)-bounded

zbMATH Keywords

independent setstring graphouter-string graphsize of representation

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph representations (geometric and intersection representations, etc.) (05C62)

Cites Work

• The Complexity of Coloring Circular Arcs and Chords
• A separator theorem for string graphs and its applications
• Separator theorems and Turán-type results for planar intersection graphs
• The max clique problem in classes of string-graphs
• Every planar graph is the intersection graph of segments in the plane
• The Rectilinear Steiner Tree Problem is $NP$-Complete
• Independent set of intersection graphs of convex objects in 2D
• The Hamiltonian circuit problem for circle graphs is NP-complete
• Intersection graphs of curves in the plane
• Coloring intersection graphs of \(x\)-monotone curves in the plane
• Title not available (Why is that?)
• Recognizing string graphs in NP
• Topology of Thin Film RC Circuits
• String graphs. II: Recognizing string graphs is NP-hard
• String graphs requiring exponential representations
• Recognizing string graphs is decidable
• An algorithm for the maximum weight independent set problem on outerstring graphs
• Weakly transitive orientations, Hasse diagrams and string graphs
• Decidability of string graphs
• Intersection graphs of rays and grounded segments
• Refining the hierarchies of classes of geometric intersection graphs
• Approximation Algorithms for Polynomial-Expansion and Low-Density Graphs
• Separators in region intersection graphs

Cited In (2)

• Outerstring Graphs are $\chi$-Bounded
• Finding geometric representations of apex graphs is \textsf{NP}-hard

This page was built for publication: On the size of outer-string representations

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