If you restrict the metric case even further and only allow planar graphs, you get even some neat approximations. For example, there exists an O(c^(1/e^2)n) eps

If you restrict the metric case even further and only allow planar graphs, you get even some neat approximations. For example, there exists an O(c^(1/e^2)n) epsilon approximation scheme: http://cs.brown.edu/~pnk/publications/tsp2005.pdf http://cs.brown.edu/~pnk/publications/tsp2005.pdf This manuscript, http://planarity.org/ http://planarity.org/ , contains most of the material in a planar graph optimization course I took a few years ago.