OUTER-FACIAL GRAPHS AND THE TRAVELING SALESMAN PROBLEM

An outer-facial graph is a planar 3-connected graph with one face havi ng a node or edge in common with every other face. It is shown that th e traveling salesman problem (TSP) in such graphs, for arbitrary edge weights, can be transformed into a variant of the TSP (called the inte rnational salesman problem (ISP)) in an associated Halin graph. In its simplest form, an ISP is obtained by partitioning the nodes of a grap h into a set of countries. A tour of minimum cost that visits each cou ntry exactly once is required, but within each country a visit may be made to any nonempty subset of the nodes. A linear system is described sufficient to define the convex hull of the incidence vectors of the feasible tours for an ISP obtained in this fashion. This linear system has size polynomial in the size of the original graph. Thus, the TSP in an outer-facial graph is reduced to a small linear programming prob lem.The traveling salesman polytope of an outer-facial graph can be ob tained as a projection of the polyhedron defined by the above system. For a class of outer-facial graphs, this fact is used to give explicit ly a defining system for the TSP. This system includes the well-known subtour elimination constraints and comb inequalities.