A combinatorial algorithm for the planar multiflow problem with demands located on three holes

Maxim A. Babenko, Alexander V. Karzanov

We consider an undirected multi(commodity)flow demand problem in which a supply graph is planar, each source-sink pair is located on one of three specified faces of the graph, and…