Shortest non intersecting path for a graph embedded in a euclidean plane (2D)

Problem Detail: 

What algorithm would you use to find the shortest path of a graph, which is embedded in an euclidean plane, such that the path should not contain any self-intersections (in the embedding)?

For example, in the graph below, you want to go from $(0,0) \rightarrow (-3,2)$. Normally, an algorithm like Dijkstra's algorithm would produce a sequence like:

$$\left[ (0,0) \stackrel {3}{\rightarrow} (0,3) \stackrel{\sqrt{2}}{\rightarrow} (1,2) \stackrel{4}{\rightarrow} (-3,2) \right] = 7+\sqrt{2}.$$

Full graph:

Shortest path:

Shortest non-intersecting path:

However, this path intersects itself on the euclidean plane, therefore I want an algorithm that would give me the shortest non-intersecting sequence, in this case:

$$\left[(0,0) \stackrel{3}{\rightarrow} (0,3) \stackrel{3}{\rightarrow} (0,6) \stackrel{5}{\rightarrow} (-3,2) \right] = 11.$$

This path is longer than the shortest path, but it is the shortest non-intersecting path.

Is there an (efficient) algorithm that can do this?

TikZ sources

• Full graph.
• Shortest path.
• Shortest non-intersecting path.

Asked By : Realz Slaw

Answered By : Jan Dvorak

It is NP-complete to even decide whether any path exists.

It is clearly possible to verify any given path is a valid path in the given graph. Thus the bounded-length problem is in NP, and so is its subset, the any-path problem.

Now, to prove NP-hardness of the any-path problem (and thus of the bounded-length problem), let's reduce SAT-CNF to this problem:

---

The global structure is a grid of wire pieces adjoined by a column of clause pieces. Logic formula is satisfiable iff there exists a non-intersecting path through the graph.

It is impossible to cross two pieces of the path, but it is neccessary to cross two logic wires. Rather, the path flow is strictly given: a wire point is given by two nodes. The sequence of the wire points through which the path passes is forced by the reduction. Logic is represented by which node is chosen. Any path can be chosen as long as it passes through all wire points.

In this diagram, the path is represented by the red curve and the logic flow is represented by the black wires:

Now let's build each component.

---

Wiring uses three tiles: the crossing, the branch point, and the vertical wire. Let's start with the hardest one:

The basic idea behind the crossing is to prepare a path for each pair of wire points and bend the possible paths enough so that all pairs except those that encode the same logic (compatible paths) cross each other. Of course we can't just say two parallel edges intersect, but we can introduce extra order-2 nodes to make two paths intersect.

Supposing the paths come from north to west and from south to east, we can: collect each path from north with its compatible path from east on a line (some incompatible paths will cross each other); cross each pair with each other by reversing the order of pairs; distribute the paths to their south and west endpoints. This is best explained by a diagram. Here, each pair of nodes represents a wire point. Paths with the same color code (carrying the same logic) don't intersect, paths a different color code do:

The branch point and the vertical wire work the same, but there are fewer paths to correlate:

The clause box follows the same logic: each literal exposes one of its paths to the reading wire, then converging to the south (if it's the northernmost term or the term to the north converges to the north) or to the north (if the term to the north converges to the south). The reading wire (one node at the endpoints) branches to become one path per literal. Each reading path then crosses the literal's true-path if the literal is negated, the false-path if it is not. Note that the converged path may or may not cross a clause boundary. For consistency, here's a diagram for $\neg A \vee \neg B$:

It is possible to generalise this reduction to encode an arbitrary tree of AND and OR gates by branching the reading wire in different way. In particular, SAT-CNF and SAT-DNF are both possible to reduce to the non-intersecting path problem in the way described as above.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/16269