6
$\begingroup$

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.

Improve this question
$\endgroup$
2
  • $\begingroup$ Not quite what you want.... cs.ucsb.edu/~teo/papers/TCSGrid.pdf $\endgroup$
    – Sariel Har-Peled
    Commented Mar 11, 2015 at 4:52
  • $\begingroup$ 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. $\endgroup$
    – reinierpost
    Commented Mar 11, 2015 at 8:51

1 Answer 1

Reset to default
5
$\begingroup$

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)

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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