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 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 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.

  • 2
    $\begingroup$ How can "geometrically nonintersecting edges" be related to TSP when every city is connected to every other city in TSP (only with different edge weights)? $\endgroup$ Oct 27 '13 at 20:10
  • $\begingroup$ 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. $\endgroup$
    – vzn
    Oct 27 '13 at 20:17
  • 1
    $\begingroup$ still not clear. if the graph is planar, it can be drawn so that no edges intersect. $\endgroup$ Oct 27 '13 at 20:25
  • $\begingroup$ 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). $\endgroup$ Oct 27 '13 at 20:44
  • 6
    $\begingroup$ 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. $\endgroup$
    – Jeffε
    Oct 28 '13 at 2:32

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 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

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

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

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 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 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.

  • $\begingroup$ so this is not a planar graph, it's a graph with edge weights given by euclidean distances between points in the plane? $\endgroup$ Oct 28 '13 at 0:05
  • $\begingroup$ @SashoNikolov edited $\endgroup$ Oct 28 '13 at 0:10
  • 5
    $\begingroup$ 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. $\endgroup$ Oct 28 '13 at 1:11
  • 4
    $\begingroup$ 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. $\endgroup$
    – Matthias
    Oct 28 '13 at 16:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.