From: gwoegi@fmatbds01.tu-graz.ac.REMOVE.at (Gerhard J. Woeginger)
Subject: Re: Euclidean TSP
Date: 2 Dec 1999 14:00:11 -0600
Newsgroups: sci.math.research
Keywords: optimal traveling saleman path is planar

In article <3hq03f0gj0tr@forum.swarthmore.edu> roconnor@interlog.com (Rory O'Connor) writes:
>From: roconnor@interlog.com (Rory O'Connor)
>Subject: Euclidean TSP
>Date: 30 Nov 1999 23:27:59 -0500

>I'm not a practising mathematician, but I'm interested in the
>following:  Given a graph Kn (possibly non-planar), with distances in
>the Euclidean plane and no 3 points collinear, is the optimal solution
>for Euclidean TSP on Kn planar?  I've searched for some reference to
>this problem, but to no avail.

>Thanks,
>Rory O'Connor

Yes, that's a folklore result. The oldest reference (that I am aware of) where 
this result is mentioned is the paper M.M. Flood: The traveling salesman 
problem. Operations Research 4 (1956), 61-75.

A good source for all kinds of results on the TSP is the book by Lawler, 
Lenstra, Rinnooy Kan & Shmoys "The traveling salesman problem - A guided tour 
of combinatorial optimization", Wiley 1985.

Gerhard 
___________________________________________________________
Gerhard J. Woeginger  (gwoegi@opt.math.tu-graz.ac.at)
==============================================================================

From: Gareth McCaughan <Gareth.McCaughan@pobox.com>
Subject: Re: Euclidean TSP
Date: 2 Dec 1999 00:00:02 -0600
Newsgroups: sci.math.research

Rory O'connor wrote:

> I'm not a practising mathematician, but I'm interested in the
> following:  Given a graph Kn (possibly non-planar), with distances in
> the Euclidean plane and no 3 points collinear, is the optimal solution
> for Euclidean TSP on Kn planar?  I've searched for some reference to
> this problem, but to no avail.

Yes.

Proof:

Suppose you have a non-planar Hamiltonian cycle. Find two
edges that cross:

      *    *
       \  /
        \/
        /\
       /  \
      *    *

Then both of these configurations

   *----*      *    *
               |    |
               |    |
               |    |
               |    |
   *----*      *    *

have length shorter than that of the "X" above (proof:
superimpose either on the "X", and apply the triangle
inequality to the two triangles formed); and one of them
must still yield a Hamiltonian cycle when substituted
for the "X" (proof: exercise.)

Therefore, any non-planar Hamiltonian cycle can be
shortened. Therefore, any shortest-length Hamiltonian
cycle is planar.

--
Gareth McCaughan  Gareth.McCaughan@pobox.com
sig under construction