Minimum Cuts and Shortest Cycles in Directed Planar Graphs via Noncrossing Shortest Paths

Hung-Chun Liang, Hsueh-I Lu

Let $G$ be an $n$-node simple directed planar graph with nonnegative edge weights. We study the fundamental problems of computing (1) a global cut of $G$ with minimum weight and (2…