Finding k partially disjoint paths in a directed planar graph

DOI10.1007/978-3-662-59204-5_13MaRDI QIDQ3295274zbMATH OpenOpenAlexFDO

Authors Alexander Schrijver

Publication date 8 July 2020

Published in Bolyai Society Mathematical Studies (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1504.00185

zbMATH Keywords

directed graphdisjoint pathsfree partially commutative groupgraph grouppartially disjoint pathsplanar graph

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Directed graphs (digraphs), tournaments (05C20) Graph algorithms (graph-theoretic aspects) (05C85) Algorithms on strings (68W32) Combinatorial optimization (90C27)

Abstract: The {it partially disjoint paths problem} is: {it given:} a directed graph, vertices $r_1,s_1,ldots,r_k,s_k$, and a set $F$ of pairs $i,j$ from $1,ldots,k$, {it find:} for each $i=1,ldots,k$ a directed $r_i-s_i$ path $P_i$ such that if $i,jinF$ then $P_i$ and $P_j$ are disjoint. We show that for fixed $k$, this problem is solvable in polynomial time if the directed graph is planar. More generally, the problem is solvable in polynomial time for directed graphs embedded on a fixed compact surface. Moreover, one may specify for each edge a subset of $1,ldots,k$ prescribing which of the $r_i-s_i$ paths are allowed to traverse this edge.

Recommendations

• Finding k Disjoint Paths in a Directed Planar Graph
• On shortest disjoint paths in planar graphs
• scientific article; zbMATH DE number 727422
• Disjoint Paths in a Planar Graph—A General Theorem
• Edge-disjoint paths in planar graphs

Cites work

• Automorphisms of graph groups.
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Combinatorics on traces
• Finding k Disjoint Paths in a Directed Planar Graph
• Graph minors. XIII: The disjoint paths problem
• scientific article; zbMATH DE number 3574107 (Why is no real title available?)
• scientific article; zbMATH DE number 475595 (Why is no real title available?)
• scientific article; zbMATH DE number 3224578 (Why is no real title available?)
• scientific article; zbMATH DE number 2221703 (Why is no real title available?)
• Inhomogeneous sorting
• Isomorphisms of Graph Groups
• Kommutationsgleichungen in semifreien gruppen
• On the Knuth-Bendix completion for concurrent processes
• The directed subgraph homeomorphism problem
• The disjoint paths problem in quadratic time
• The word problem for free partially commutative groups

Cited in

(9)

• Finding edge-disjoint paths in partial \(k\)-trees
• A tight lower bound for edge-disjoint paths on planar DAGs
• Necessary Condition for Path Partitioning Constraints
• scientific article; zbMATH DE number 508833 (Why is no real title available?)
• Finding k Disjoint Paths in a Directed Planar Graph
• scientific article; zbMATH DE number 727422 (Why is no real title available?)
• Vertex disjoint paths in upward planar graphs
• A Tight Lower Bound for Edge-Disjoint Paths on Planar DAGs
• Finding edge-disjoint paths in partial k-trees

This page was built for publication: Finding \(k\) partially disjoint paths in a directed planar graph

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3295274)