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

Preprint · Hung-Chun Liang, Hsueh-I Lu

- Archive id: arxiv:1703.07964
- Published: 2017-03-23
- Venue: SIAM Journal on Discrete Mathematics 31 (1): 454-476, 2017
- DOI: https://doi.org/10.1137/16m1057152
- arXiv: https://arxiv.org/abs/1703.07964
- Source URL: https://arxiv.org/abs/1703.07964
- PDF: https://arxiv.org/pdf/1703.07964
- Provenance: arxiv

## Abstract

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) a~cycle of $G$ with minimum weight. The best previously known algorithm for the former problem, running in $O(n\\log^3 n)$ time, can be obtained from the algorithm of \\Lacki, Nussbaum, Sankowski, and Wulff-Nilsen for single-source all-sinks maximum flows. The best previously known result for the latter problem is the $O(n\\log^3 n)$-time algorithm of Wulff-Nilsen. By exploiting duality between the two problems in planar graphs, we solve both problems in $O(n\\log n\\log\\log n)$ time via a divide-and-conquer algorithm that finds a shortest non-degenerate cycle. The kernel of our result is an $O(n\\log\\log n)$-time algorithm for computing noncrossing shortest paths among nodes well ordered on a common face of a directed plane graph, which is extended from the algorithm of Italiano, Nussbaum, Sankowski, and Wulff-Nilsen for an undirected plane graph.

_Abstract reproduced under CC0-1.0 (arXiv descriptive metadata)._

---
Space Kitty Archive · https://space-kitty.com · API: https://space-kitty.com/api/v1 · MCP: https://space-kitty.com/mcp · Premium: $0.20/request via x402 (Base Sepolia (testnet)). Metadata: arXiv (CC0), OpenAlex (CC0), Europe PMC (CC BY/CC0 works), ClinicalTrials.gov.