On the size of outer-string representations

DOI10.4230/LIPICS.SWAT.2018.10MaRDI QIDQ5116474zbMATH OpenFDO

Authors Ahmad Biniaz, Martin Derka, Therese Biedl

Publication date 25 August 2020

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)

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

Cites work

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

Cited in

(2)

• Finding geometric representations of apex graphs is \textsf{NP}-hard
• Outerstring graphs are \(\chi \)-bounded

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)