In the worst case, the Traveling Salesperson Problem (TSP) is mostly accepted to take exponential runtime in terms of $|V|$ and $|E|$ (the number of vertices and edges respectively). But for many real-world TSP problems, while $|E|$ and $|V|$ may be large, you often have many other properties of the graph that one would consider to make the problem tractable. E.g. how small the mincut is, how small the treewidth is, how small the max degree of nodes is, whether the graph is planar/obeys the triangle inequality, etc.
Are there any TSP algorithms with decently efficient run-times given in terms of these alternative metrics for the graph "size"? Approximate algorithms are fine too, I think.
