<p>Let it be Euclidean graph: each vertex is a point on the 2D plane, so the weight of each edge is the Euclidean distance between the vertices.</p>

<p>I tell you what I am going to prove that and then I try proving. </p>

<p>So first I am going to show you that each planar graph with <a href="https://en.wikipedia.org/wiki/Hamiltonian_cycle" rel="nofollow noreferrer">Hamiltonian circuit</a> path, that have intersections, could be easily changed to shorter path, then I show you that those changes could be done in short time in compare to exponential time, and then I show you why I think that there are only very few options to find a non intersecting Hamiltonian circuit path and why I think that one of those options is the TSP optimal path.</p>

<p>So first I want to prove you and show you a method to remove intersections from the graph.
Lets start with a small example for intersection</p>

<p><img src="https://i.sstatic.net/G8EHW.png" alt="enter image description here"></p>

<p>In this drawing you can see the edges $AB$ and $DC$ intersect with each other. </p>

<p>I am going to switch between the edges so it will look like this:</p>

<p><img src="https://i.sstatic.net/2HW77.png" alt="enter image description here"></p>

<p>In orange you can see the new edges, and now I am going to show you why those new edges are shorter. But before that I want to notice that this is a legal action in a graph, I do not break the rule that there would be no more than 2 edges connected to single vertex.</p>

<p><img src="https://i.sstatic.net/yqqrk.png" alt="enter image description here"></p>

<p>At this image I added to lines for calculations: EO is perpendicular to AC, and EF is perpendicular to DF. So now we have triangles with 90 degree angle and we can tell that $AO$ is bigger than $AE$ and $OC$ is bigger than $EC$ and so is $DO$ is bigger than $DF$ and $OB$ is bigger than $FB$. So we may say that $AE + EC + DF + FB &lt; AO + OB + OC + OD$</p>

<p>And so we can say $AC + DB &lt; AB + DC$. So by solving intersections in graph we can actually find a shorter paths and this is the reason there couldn't be any intersections in TSP optimal route.</p>

<p>But even more interesting than that is calculating by just how much we cut the graph. I do not know how exactly explain this mathematically, I hope someone will be able to help me here, but try comparing $AB + DC$ to $AC + DB$ what is the difference between them. I think we need to look at the average difference between all the edges, and this difference cannot be very small in compare to $N$(This is the part that I do not know how to explain) so there could not be many "Fixes" like that, that we can do, so the efficiency of finding non intersecting graph is $O(CN^2)$ where $C$ is not a big number in compare to $N$. You can find <a href="http://tsp-vs-world.blogspot.co.il/2013/10/big-plane.html" rel="nofollow noreferrer">here</a> a pasado code that I wrote to implement this.</p>

<p>Also I want to share with you the results of my guesses using this algorithm to guess what is the optimal toure. I used a sample data from <a href="http://www.math.uwaterloo.ca/tsp/world/countries.html" rel="nofollow noreferrer">this</a> site, because I can't really know if my guess is the optimal toure or not. And so, it took me 122 millisecond to guess the optimal tour of 39 cities. 0 or 16 milliseconds for 29 cities and just a bit less than 3 sec guessing the optimal tour of 194 cities. Each of those numbers is the worst and also the average case of 50 tries on each input.</p>

<p>Also I been trying to build a small test tool to get some feeling about how many non intersecting routes there are, and it looks like between $0.5N$ to $3N$.</p>

<p>I can tell you that this subject is very interesting, I already spent weeks on that and continue the work.</p>

CC BY-SA 3.0
2013-10-28T00:05:58.397Z
so this is not a planar graph, it's a graph with edge weights given by euclidean distances between points in the plane?
Sasho Nikolov
CC BY-SA 3.0
2013-10-28T00:10:52.200Z
@SashoNikolov edited
Ilya Gazman
CC BY-SA 3.0
2013-10-28T01:11:21.553Z
Ya, but the question talks about planar graphs. So this is not an answer to the question. In any case, ideas like this are used in Arora's PTAS for euclidean tsp. See Chapter 10.1. of Williamson and Shmoys' approximation algorithms book.
Sasho Nikolov
CC BY-SA 3.0
2013-10-28T16:46:49.420Z
I don't fully understand what you are trying to do but van Leeuwen and Schoon published a paper in WG in 1981 titled "Untangling a traveling salesman tour in the plane". In this paper they give an efficient algorithm to find a tour without intersections that is not longer than some arbitrary initial tour.
Matthias
CC BY-SA 3.0
2013-10-27T22:26:16.100Z
2013-10-28T00:10:39.370Z
2013-10-28T00:10:39.370Z
Ilya Gazman
<p>Consider the problem of finding smaller "non-intersecting" circuits or paths in graphs embedded in the euclidean plane (visiting all vertices) in the sense of geometric intersections of edges plotted as lines. This is clearly closely related to TSP, <a href="http://en.wikipedia.org/wiki/Travelling_salesman_problem" rel="nofollow noreferrer">travelling salesman problem</a> for euclidean plane embedded graphs. Is it virtually the same problem or not?</p>

<blockquote>
  <p>Is there research on and/or are there algorithms that enumerate small non-intersecting circuits/paths of planar graphs?</p>
</blockquote>

<p>In other words the $n$ graph vertices are already given as 2d coordinates of points. The problem is to find a $n$-vertex path or cycle through all the points such that when the edges are plotted as lines, the edges/lines do not cross.</p>

<p>I did not find any literature directly on this in various online searches.</p>

<p>A second somewhat related question: Is the <a href="https://cs.stackexchange.com/questions/16269/shortest-non-intersecting-path-for-a-graph-embedded-in-a-euclidean-plane-2d">shortest non intersecting path for a graph embedded in the euclidean plane</a> on cs.se. This asks basically the same question for a path with $m$ points, $m \leq n$.</p>

<p>The question is related to experiments &amp; questions by a new cs.se user <a href="https://cs.stackexchange.com/users/10572/babibu">babibu</a>.</p>

CC BY-SA 3.0
2013-10-27T20:17:45.520Z
oops, not clear? the reference to "nonintersecting" is wrt edge lines "crossing over" other edge lines. two edge lines "meeting" at a vertex point are not considered "intersecting" for this question.
vzn
CC BY-SA 3.0
2013-10-27T20:25:09.173Z
still not clear. if the graph is planar, it can be drawn so that no edges intersect.
Sasho Nikolov
CC BY-SA 3.0
2013-10-27T20:44:59.883Z
Even if a graph is known to be planar, drawing it is not a trivial question. Hence, considering the question of *drawing planar graphs* one approach consists of traversing paths that include all vertices in the graph. This is the TSP **without costs**. I think the question is relevant since some algorithms for drawing planar graphs are known to be polynomial but these are restricted just to a few cases. As for myself, I know nothing about the complexity of drawing planar graphs in the general case but I won't be much surprised if it is exponential (and it should if it is related to TSP).
Carlos Linares López
CC BY-SA 3.0
2013-10-28T02:32:15.593Z
_Even if a graph is known to be planar, drawing it is not a trivial question._ — Not true.  There are several well-known algorithms for drawing aribtrary planar graphs in the plane in O(n) time.
Jeffε
CC BY-SA 3.0
2013-10-28T15:03:35.493Z
oops, sorry all. messed up, this was formulated incorrectly. think the correct phrasing was "graph embedded in euclidean plane" which is different than "planar graph". am going to edit although the current votes have presumably pushed it off the home pg.
vzn
CC BY-SA 3.0
2014-03-27T15:27:02.423Z
hi all since this post have heard about [3-opt](http://en.wikipedia.org/wiki/3-opt) for TSP which is basically the area of research requested
vzn
CC BY-SA 3.0
2014-03-27T16:19:27.120Z
see eg [equivalence property in hamiltonian graphs](http://cstheory.stackexchange.com/questions/4343/searching-for-name-of-equivalence-property-in-hamiltonian-paths) tcs.se or [how does 3OPT for TSP work?](http://cs.stackexchange.com/questions/19808/how-does-the-3-opt-algorithm-for-tsp-work) cs.se
vzn
<reference-request><graph-algorithms><optimization><planar-graphs>
Attacking TSP via small nonintersecting circuits
vzn
# Attacking TSP via small nonintersecting circuits

(Asked by: username_0 on 2013-10-27)

Consider the problem of finding smaller "non-intersecting" circuits or paths in graphs embedded in the euclidean plane (visiting all vertices) in the sense of geometric intersections of edges plotted as lines. This is clearly closely related to TSP, [travelling salesman problem](http://en.wikipedia.org/wiki/Travelling_salesman_problem) for euclidean plane embedded graphs. Is it virtually the same problem or not?

> Is there research on and/or are there algorithms that enumerate small non-intersecting circuits/paths of planar graphs?

In other words the $n$ graph vertices are already given as 2d coordinates of points. The problem is to find a $n$-vertex path or cycle through all the points such that when the edges are plotted as lines, the edges/lines do not cross.

I did not find any literature directly on this in various online searches.

A second somewhat related question: Is the [shortest non intersecting path for a graph embedded in the euclidean plane](https://cs.stackexchange.com/questions/16269/shortest-non-intersecting-path-for-a-graph-embedded-in-a-euclidean-plane-2d) on cs.se. This asks basically the same question for a path with $m$ points, $m \leq n$.

The question is related to experiments & questions by a new cs.se user [babibu](https://cs.stackexchange.com/users/10572/babibu).

**Tags:** reference-request, graph-algorithms, optimization, planar-graphs

> **Comments:**
> **username_0**: oops, not clear? the reference to "nonintersecting" is wrt edge lines "crossing over" other edge lines. two edge lines "meeting" at a vertex point are not considered "intersecting" for this question.  
> **username_1**: still not clear. if the graph is planar, it can be drawn so that no edges intersect.  
> **username_2**: Even if a graph is known to be planar, drawing it is not a trivial question. Hence, considering the question of *drawing planar graphs* one approach consists of traversing paths that include all vertices in the graph. This is the TSP **without costs**. I think the question is relevant since some algorithms for drawing planar graphs are known to be polynomial but these are restricted just to a few cases. As for myself, I know nothing about the complexity of drawing planar graphs in the general case but I won't be much surprised if it is exponential (and it should if it is related to TSP).  
> **username_3**: _Even if a graph is known to be planar, drawing it is not a trivial question._ — Not true.  There are several well-known algorithms for drawing aribtrary planar graphs in the plane in O(n) time.  
> **username_0**: oops, sorry all. messed up, this was formulated incorrectly. think the correct phrasing was "graph embedded in euclidean plane" which is different than "planar graph". am going to edit although the current votes have presumably pushed it off the home pg.  
> **username_0**: hi all since this post have heard about [3-opt](http://en.wikipedia.org/wiki/3-opt) for TSP which is basically the area of research requested  
> **username_0**: see eg [equivalence property in hamiltonian graphs](http://cstheory.stackexchange.com/questions/4343/searching-for-name-of-equivalence-property-in-hamiltonian-paths) tcs.se or [how does 3OPT for TSP work?](http://cs.stackexchange.com/questions/19808/how-does-the-3-opt-algorithm-for-tsp-work) cs.se  

---

## 1 answers

### Answer by username_4 on 2013-10-27. Score: -6

Let it be Euclidean graph: each vertex is a point on the 2D plane, so the weight of each edge is the Euclidean distance between the vertices.

I tell you what I am going to prove that and then I try proving.

So first I am going to show you that each planar graph with [Hamiltonian circuit](https://en.wikipedia.org/wiki/Hamiltonian_cycle) path, that have intersections, could be easily changed to shorter path, then I show you that those changes could be done in short time in compare to exponential time, and then I show you why I think that there are only very few options to find a non intersecting Hamiltonian circuit path and why I think that one of those options is the TSP optimal path.

So first I want to prove you and show you a method to remove intersections from the graph.
Lets start with a small example for intersection

![enter image description here](https://i.sstatic.net/G8EHW.png)

In this drawing you can see the edges $AB$ and $DC$ intersect with each other.

I am going to switch between the edges so it will look like this:

![enter image description here](https://i.sstatic.net/2HW77.png)

In orange you can see the new edges, and now I am going to show you why those new edges are shorter. But before that I want to notice that this is a legal action in a graph, I do not break the rule that there would be no more than 2 edges connected to single vertex.

![enter image description here](https://i.sstatic.net/yqqrk.png)

At this image I added to lines for calculations: EO is perpendicular to AC, and EF is perpendicular to DF. So now we have triangles with 90 degree angle and we can tell that $AO$ is bigger than $AE$ and $OC$ is bigger than $EC$ and so is $DO$ is bigger than $DF$ and $OB$ is bigger than $FB$. So we may say that $AE + EC + DF + FB < AO + OB + OC + OD$

And so we can say $AC + DB < AB + DC$. So by solving intersections in graph we can actually find a shorter paths and this is the reason there couldn't be any intersections in TSP optimal route.

But even more interesting than that is calculating by just how much we cut the graph. I do not know how exactly explain this mathematically, I hope someone will be able to help me here, but try comparing $AB + DC$ to $AC + DB$ what is the difference between them. I think we need to look at the average difference between all the edges, and this difference cannot be very small in compare to $N$(This is the part that I do not know how to explain) so there could not be many "Fixes" like that, that we can do, so the efficiency of finding non intersecting graph is $O(CN^2)$ where $C$ is not a big number in compare to $N$. You can find [here](http://tsp-vs-world.blogspot.co.il/2013/10/big-plane.html) a pasado code that I wrote to implement this.

Also I want to share with you the results of my guesses using this algorithm to guess what is the optimal toure. I used a sample data from [this](http://www.math.uwaterloo.ca/tsp/world/countries.html) site, because I can't really know if my guess is the optimal toure or not. And so, it took me 122 millisecond to guess the optimal tour of 39 cities. 0 or 16 milliseconds for 29 cities and just a bit less than 3 sec guessing the optimal tour of 194 cities. Each of those numbers is the worst and also the average case of 50 tries on each input.

Also I been trying to build a small test tool to get some feeling about how many non intersecting routes there are, and it looks like between $0.5N$ to $3N$.

I can tell you that this subject is very interesting, I already spent weeks on that and continue the work.

> **Comments:**
> **username_1**: so this is not a planar graph, it's a graph with edge weights given by euclidean distances between points in the plane?  
> **username_4**: @SashoNikolov edited  
> **username_1**: Ya, but the question talks about planar graphs. So this is not an answer to the question. In any case, ideas like this are used in Arora's PTAS for euclidean tsp. See Chapter 10.1. of Williamson and Shmoys' approximation algorithms book.  
> **username_5**: I don't fully understand what you are trying to do but van Leeuwen and Schoon published a paper in WG in 1981 titled "Untangling a traveling salesman tour in the plane". In this paper they give an efficient algorithm to find a tour without intersections that is not longer than some arbitrary initial tour.  

---

