Multi-Terminal Shortest Paths in Unit-Weight Planar Graphs in Linear Time
share
Given a set of terminal pairs on the external face of a planar graph with unit edge weights, we give a linear-time algorithm to compute a set of non-crossing shortest paths joining each terminal pair, if it exists.
READ FULL TEXT