2002 · 115 citations · 9 references
ComputingComputer ScienceAlgorithmsComputational GeometryOptimizationApproximation AlgorithmsCombinatorial OptimizationGeometric ApproximationGraph AlgorithmsShortest Path AlgorithmsTransportation ProblemsApproximation Algorithms For Shortest PathsPlanar Graph AlgorithmsPolynomial-time Approximation SchemeShortest Path In Planar GraphsTraveling Salesman ApproximationTraveling Salesman ProblemTraveling Salesperson ProblemTraveling Salesperson Problem Approximation
We consider the special case of the traveling salesman problem (TSP) in which the distance metric is the shortest-path metric of a planar unweighted graph. We present a polynomial-time approximation scheme (PTAS) for this problem.
9
A Separator Theorem for Planar Graphs
Richard J. Lipton, Robert E. Tarjan · SIAM Journal on Applied Mathematics · 1979 · 1.4K citations
Approximation algorithms for NP-complete problems on planar graphs
Brenda S. Baker · Journal of the ACM · 1994 · 973 citations · Full text
Applications of a Planar Separator Theorem
Richard J. Lipton, Robert E. Tarjan · SIAM Journal on Computing · 1980 · 646 citations