Shortest Vertex-Disjoint Two-Face Paths in Planar Graphs

Authors Éric Colin de Verdiére, Alexander Schrijver



PDF
Thumbnail PDF

File

LIPIcs.STACS.2008.1347.pdf
  • Filesize: 194 kB
  • 12 pages

Document Identifiers

Author Details

Éric Colin de Verdiére
Alexander Schrijver

Cite AsGet BibTex

Éric Colin de Verdiére and Alexander Schrijver. Shortest Vertex-Disjoint Two-Face Paths in Planar Graphs. In 25th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 1, pp. 181-192, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)
https://doi.org/10.4230/LIPIcs.STACS.2008.1347

Abstract

Let $G$ be a directed planar graph of complexity~$n$, each arc having a nonnegative length. Let $s$ and~$t$ be two distinct faces of~$G$; let $s_1,ldots,s_k$ be vertices incident with~$s$; let $t_1,ldots,t_k$ be vertices incident with~$t$. We give an algorithm to compute $k$ pairwise vertex-disjoint paths connecting the pairs $(s_i,t_i)$ in~$G$, with minimal total length, in $O(knlog n)$ time.
Keywords
  • Algorithm
  • planar graph
  • disjoint paths
  • shortest path

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail