Embedding Planar Graphs into Low-Treewidth Graphs with Applications to Efficient Approximation Schemes for Metric Problems

DOI10.1137/1.9781611975482.66zbMath1431.68093OpenAlexW4237350530MaRDI QIDQ5236250

Eli Fox-Epstein, Aaron Schild, Philip N. Klein

Publication date: 15 October 2019

Published in: Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/1.9781611975482.66

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Planar graphs; geometric and topological aspects of graph theory (05C10) Approximation algorithms (68W25)

Related Items (1)

The parameterized hardness of the \(k\)-center problem in transportation networks

This page was built for publication: Embedding Planar Graphs into Low-Treewidth Graphs with Applications to Efficient Approximation Schemes for Metric Problems