Shortest vertex-disjoint two-face paths in planar graphs

DOI10.1145/1921659.1921665zbMath1295.05243OpenAlexW2111716715MaRDI QIDQ3189001

Éric Colin de Verdière, Alexander Schrijver

Publication date: 9 September 2014

Published in: ACM Transactions on Algorithms (Search for Journal in Brave)

Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2008/1347/

zbMATH Keywords

shortest pathplanar graphdisjoint paths

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Distance in graphs (05C12) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Directed graphs (digraphs), tournaments (05C20)

Related Items (9)

Non-Crossing Shortest Paths in Undirected Unweighted Planar Graphs in Linear Time ⋮ Towards Single Face Shortest Vertex-Disjoint Paths in Undirected Planar Graphs ⋮ Inserting Multiple Edges into a Planar Graph ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Shortest \((A+B)\)-path packing via hafnian ⋮ Walking through waypoints ⋮ The directed 2-linkage problem with length constraints ⋮ Shortest Two Disjoint Paths in Polynomial Time

This page was built for publication: Shortest vertex-disjoint two-face paths in planar graphs