Optimality program in segment and string graphs

DOI10.1007/s00453-019-00568-7zbMath1423.68331MaRDI 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 graphs; segment graphs; subexponential algorithms; ETH

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68R10: Graph theory (including graph drawing) in computer science

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

Related Items

Unnamed Item, Computing list homomorphisms in geometric intersection graphs, Clique-based separators for geometric intersection graphs, 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