An approximation algorithm for fully planar edge-disjoint paths

Chien-Chung Huang, Mathieu Mari, Claire Mathieu, Kevin Schewior, Jens Vygen

Research output: Contribution to journalJournal articleResearchpeer-review


We devise a constant-factor approximation algorithm for the maximization version of the edge-disjoint paths problem if the supply graph together with the demand edges forms a planar graph. By planar duality, this is equivalent to packing cuts in a planar graph such that each cut contains exactly one demand edge. We also show that the natural linear programming relaxations have constant integrality gap, yielding an approximate max-multiflow min-multicut theorem.
Original languageEnglish
JournalSIAM Journal on Discrete Mathematics
Issue number2
Pages (from-to)752-769
Publication statusPublished - 2021
Externally publishedYes


Dive into the research topics of 'An approximation algorithm for fully planar edge-disjoint paths'. Together they form a unique fingerprint.

Cite this