Traveling Salesman Tour on a Road Map

This page demonstrates an implementation of a linear-time approximation scheme for traveling salesman in a planar graph. (However, for this demo the parameters are set in such a way that the approximation ratio is not guaranteed.) Pan and zoom to get the region for which you want a tour. Clicking the button computes an approximately optimal tour on the largest component of the graph defined by the visible part of the road map. Once the tour has been computed, use the slider to show the tour.