Decidability of string graphs

DOI10.1145/380752.380807zbMath1323.68307OpenAlexW1985534820MaRDI QIDQ5175975

Daniel Štefanković, Marcus Schaefer

Publication date: 27 February 2015

Published in: Proceedings of the thirty-third annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/380752.380807

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) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (7)

Drawing interactive Euler diagrams from region connection calculus specifications ⋮ Drawing Euler Diagrams from Region Connection Calculus Specifications with Local Search ⋮ Crossing-constrained hierarchical drawings ⋮ Recognizing string graphs in NP ⋮ Crossing Numbers and Parameterized Complexity ⋮ Unnamed Item ⋮ Topological graphs with no large grids

Cites Work

• A constant-factor approximation algorithm for the k -median problem (extended abstract)

This page was built for publication: Decidability of string graphs