Optimality program in segment and string graphs

DOI10.1007/s00453-019-00568-7zbMath1423.68331OpenAlexW2926426864MaRDI QIDQ5920196

Édouard Bonnet, Paweł Rzążewski

Publication date: 21 May 2019

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-019-00568-7

zbMATH Keywords

string graphssegment graphssubexponential algorithmsETH

Mathematics Subject Classification ID

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 (4)

Computing list homomorphisms in geometric intersection graphs ⋮ Clique-based separators for geometric intersection graphs ⋮ Unnamed Item ⋮ Subexponential-time algorithms for finding large induced sparse subgraphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The clique problem in ray intersection graphs
• Fixed points, Nash equilibria, and the existential theory of the reals
• A simplified NP-complete satisfiability problem
• Linearity of grid minors in treewidth with applications through bidimensionality
• A bipartite strengthening of the crossing Lemma
• String graphs. II: Recognizing string graphs is NP-hard
• String graphs requiring exponential representations
• Intersection graphs of segments
• Quickly excluding a planar graph
• Which problems have strongly exponential complexity?
• Integer realizations of disk and segment graphs
• On the Cutting Edge: Simplified O(n) Planarity by Edge Addition
• Optimal Parameterized Algorithms for Planar Facility Location Problems Using Voronoi Diagrams
• Subexponential parameterized algorithms on bounded-genus graphs and H -minor-free graphs
• Parameterized Complexity of Independence and Domination on Geometric Graphs
• Applications of a Planar Separator Theorem
• Approximation algorithms for NP-complete problems on planar graphs
• Quasi-Polynomial Time Approximation Scheme for Sparse Subsets of Polygons
• Separators in region intersection graphs
• Geometric separation and exact solutions for the parameterized independent set problem on disk graphs
• An induced subgraph characterization of domination perfect graphs
• Finding, Hitting and Packing Cycles in Subexponential Time on Unit Disk Graphs
• Every planar graph is the intersection graph of segments in the plane
• Approximation Schemes for Independent Set and Sparse Subsets of Polygons
• Bidimensional Parameters and Local Treewidth
• A QPTAS for Maximum Weight Independent Set of Polygons with Polylogarithmically Many Vertices
• Applications of a New Separator Theorem for String Graphs
• Near-Optimal Separators in String Graphs
• Graph Drawing
• Optimality program in segment and string graphs
• Recognizing string graphs in NP
• On the complexity of \(k\)-SAT

This page was built for publication: Optimality program in segment and string graphs