14
$\begingroup$

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:

enter image description here

Shortest path:

enter image description here

Shortest non-intersecting path:

enter image description here

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

$\endgroup$
  • 2
    $\begingroup$ Nice problem! (+1). Can you say anything about the application or context where this problem arises? I'm intrigued. (P.S. On a separate note: The obvious way out of this conundrum is to see if you can introduce a new vertex for every intersection point, i.e., every point where one edge can intersect another edge. However I realize that for some/many applications this might not be possible.) $\endgroup$ – D.W. Oct 21 '13 at 0:41
  • 2
    $\begingroup$ @D.W. this is me reformulating Babibu's ill-worded burning donkey/pony problem; the application is his Euclidean TSP heuristic algorithm, I am not exactly sure how he intends to use it, but I imagine he wants to know if he can find a path between two points, when he already visited several others (Euclidean TSP's optimal tour will be non-intersecting). And yes, if you can introduce new nodes, that would be great, but the question is if you can't (and ofc you can't introduce new cities for Euclidean TSP). $\endgroup$ – Realz Slaw Oct 21 '13 at 0:57
  • 1
    $\begingroup$ Let me try to convert the path existence problem to 3SAT. Making a way to cross two signals while not crossing two paths seems the biggest challenge. $\endgroup$ – John Dvorak Oct 21 '13 at 3:20
  • 1
    $\begingroup$ Yep. I meant solving SAT through this. $\endgroup$ – John Dvorak Oct 21 '13 at 4:23
  • 2
    $\begingroup$ asked similar question for $n$-point paths/cycles & its relation to TSP, tcs.se $\endgroup$ – vzn Oct 28 '13 at 17:54
12
$\begingroup$

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:

grid of wires on the left, column of clause pieces on the right.

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:

graphical depiction of the above

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

two pairs of paths are sufficient here. The wire is essentially a branch point with the branch destroyed

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

enter image description here

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.

$\endgroup$
  • $\begingroup$ Wow, well done man. I haven't reviewed it yet, but the work you put in is amazing. $\endgroup$ – Realz Slaw Oct 21 '13 at 7:48
  • $\begingroup$ OK, I just want to summarize my understanding: using the first gadget, one can cross any two literal-path pairs and maintain the paths used. Therefore, one doesn't have to worry about planarity for laying out the paths (like the xor gadget in PlanarCircuitSat does for circuits). Then using the final gadget, one can create arbitrary logical clauses (no longer having to worry about planarity). Is this correct? $\endgroup$ – Realz Slaw Oct 22 '13 at 3:52
  • $\begingroup$ This seems correct but you have to ensure two things for a general layout: That you are able to power all gadgets with an NIP path (this should always be possible - if a path becomes stuck in the center, you can introduce wire-gadgets to bring lone ends of the path together) and that all paths in the reading wire cross each other in such a way that it is not possible to reverse within the wire (it seems to me that it is guaranteed if there are no true-clauses (not crossing any literal) and if all clauses are on the outside of the circuit (on the same face the start and end are)). $\endgroup$ – John Dvorak Oct 22 '13 at 4:15
  • $\begingroup$ ensuring that all paths in the reading wire cross each other is easy - if you want to be sure, just branch off n paths, then cross all of them right away. I think this is never neccessary, however. $\endgroup$ – John Dvorak Oct 22 '13 at 4:22
  • 1
    $\begingroup$ I used OpenOffice Draw for the global structure, and [yEd](www.yworks.com/products/yed) for the rest. Should I edit that in (with <sub>)? $\endgroup$ – John Dvorak Oct 22 '13 at 4:36
-1
$\begingroup$

the problem seems to date to Turan 1944. this looks like a good survey of theory and algorithms, the Crossing Number of Graphs: Theory and Computation by Mutzel. wikipedia has some info under crossing number of graphs

$\endgroup$
  • 1
    $\begingroup$ Maybe this is better as a comment? $\endgroup$ – Juho Oct 22 '13 at 18:29
  • $\begingroup$ it scientifically answers the basic question "what algorithm would you use" $\endgroup$ – vzn Oct 22 '13 at 20:16
  • 1
    $\begingroup$ Whilst this may theoretically answer the question, it would be preferable to include the essential parts of the answer here, and provide the link for reference. $\endgroup$ – John Dvorak Oct 23 '13 at 6:22
  • $\begingroup$ jan cites a ref from stackexchange meta. while thats a valid idea, the role of citations in science/mathematics is different than a programming tips site.... [admittedly the ref is not available to me currently for a more detailed answer].. anyway it is quite possible something like jans construction, while useful/worthwhile, is already in the literature and in science, its part of the standard process/best practices to [attempt to] locate it.... $\endgroup$ – vzn Oct 25 '13 at 15:45

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.