<p>The following paper establishes NP-hardness of essentially all non-trivial questions in this direction:</p>

<blockquote>
  <p>Jan Kratochvíl, Anna Lubiw, Jaroslav Nesetril:
  Noncrossing Subgraphs in Topological Layouts. SIAM J. Discrete Math. 4(2): 223-244 (1991)</p>
</blockquote>

CC BY-SA 3.0
2015-03-11T17:45:03.750Z
2015-03-11T17:45:03.750Z
Gamow
<p>Let $G$ be an undirected  graph, given with a planar drawing. 
We do not assume $G$ is a planar graph, we just fix a planar representation of it, such that each vertex is represented by a distinct point in the plane, and each edge is represented by a continuous planar curve between its endpoints. Assume that no other vertex can lie on such a curve, but we allow unlimited intersections among these edge-curves.</p>

<p>Let $s,t$ be two distinguished vertices in $G$. We say that two $s-t$ paths are <strong>geometrically disjoint,</strong> (with respect to the given drawing), if their geometric representations  do not share any point, other than $s$ and $t$. Note that it is a stronger requirement than being (internally) vertex disjoint in the graph theoretic sense, because they may be vertex disjoint, yet they may share some intersection point of the curves that represent the edges, when we follow through the paths as geometric curves.</p>

<p><strong>Questions:</strong> </p>

<ol>
<li><p>What is the complexity of finding the maximum number of geometrically disjoint $s-t$ paths? </p></li>
<li><p>How about the special case when the edges are restricted to be straight lines?</p></li>
</ol>

<p><strong>Remark:</strong> Finding the max number of vertex- or edge-disjoint paths is well known to be solvable by network flow techniques in polynomial time. Does the geometric requirement make the problem harder?</p>

<p><strong>Edit:</strong> Let us assume that the vertices have polynomially bounded integer coordinates, in terms of the number of vertices. Furthermore, assume an oracle is available that can determine for any two edge-curves whether they intersect or not. When the edges are represented by straight lines, this is straightforward, but in the general case it may be hard to decide whether two curves intersect.</p>

CC BY-SA 3.0
2015-03-11T04:52:35.683Z
Not quite what you want....
http://www.cs.ucsb.edu/~teo/papers/TCSGrid.pdf
Sariel Har-Peled
CC BY-SA 3.0
2015-03-11T08:51:00.143Z
For 1, don't you need to make additional assumptions on the cost of determining whether two curves intersect? It depends on the kinds of curves you allow.
reinierpost
<cc.complexity-theory><graph-theory><graph-algorithms><computational-geometry>
Maximum number of geometrically disjoint paths - is the complexity known?
Andras Farago
# Maximum number of geometrically disjoint paths - is the complexity known?

(Asked by: username_0 on 2015-03-10)

Let $G$ be an undirected graph, given with a planar drawing.
We do not assume $G$ is a planar graph, we just fix a planar representation of it, such that each vertex is represented by a distinct point in the plane, and each edge is represented by a continuous planar curve between its endpoints. Assume that no other vertex can lie on such a curve, but we allow unlimited intersections among these edge-curves.

Let $s,t$ be two distinguished vertices in $G$. We say that two $s-t$ paths are **geometrically disjoint,** (with respect to the given drawing), if their geometric representations do not share any point, other than $s$ and $t$. Note that it is a stronger requirement than being (internally) vertex disjoint in the graph theoretic sense, because they may be vertex disjoint, yet they may share some intersection point of the curves that represent the edges, when we follow through the paths as geometric curves.

**Questions:**

1. What is the complexity of finding the maximum number of geometrically disjoint $s-t$ paths?
2. How about the special case when the edges are restricted to be straight lines?

**Remark:** Finding the max number of vertex- or edge-disjoint paths is well known to be solvable by network flow techniques in polynomial time. Does the geometric requirement make the problem harder?

**Edit:** Let us assume that the vertices have polynomially bounded integer coordinates, in terms of the number of vertices. Furthermore, assume an oracle is available that can determine for any two edge-curves whether they intersect or not. When the edges are represented by straight lines, this is straightforward, but in the general case it may be hard to decide whether two curves intersect.

**Tags:** cc.complexity-theory, graph-theory, graph-algorithms, computational-geometry
> **Comments:**
> **username_1**: Not quite what you want.... http://www.cs.ucsb.edu/~teo/papers/TCSGrid.pdf  
> **username_2**: For 1, don't you need to make additional assumptions on the cost of determining whether two curves intersect? It depends on the kinds of curves you allow.  

---

## 1 answers

### Answer by username_3 on 2015-03-11. Score: 5 | Accepted answer

The following paper establishes NP-hardness of essentially all non-trivial questions in this direction:

> Jan Kratochvíl, Anna Lubiw, Jaroslav Nesetril:
> Noncrossing Subgraphs in Topological Layouts. SIAM J. Discrete Math. 4(2): 223-244 (1991)


---

