, } of clusters of terminals, all lying on the outer face of G. Output: An optimal multi-cluster cut for the input graph

C. Bentz, On the complexity of the multicut problem in bounded treewidth graphs and digraphs, Discrete Applied Mathematics, vol.156, pp.1908-1917, 2008.
URL : https://hal.archives-ouvertes.fr/hal-01126374

C. Bentz, A simple algorithm for multicuts in planar graphs with outer terminals, Discrete Applied Mathematics, vol.157, pp.1959-1964, 2009.
URL : https://hal.archives-ouvertes.fr/hal-01126379

C. Bentz, A Polynomial-Time Algorithm for Planar Multicuts with Few Source-Sink Pairs, Proceedings IPEC, pp.109-119, 2012.
URL : https://hal.archives-ouvertes.fr/hal-01126381

N. Bousquet, J. Daligault, and S. Thomassé, Multicut is FPT. Proceedings STOC, pp.459-468, 2011.
URL : https://hal.archives-ouvertes.fr/lirmm-00741933

D. Z. Chen and X. Wu, Efficient algorithms for k-terminal cuts on planar graphs, Algorithmica, vol.38, pp.299-316, 2004.

É. Colin-de-verdière, Multicuts in Planar and Bounded-Genus Graphs with Bounded Number of Terminals, Algorithmica, vol.78, pp.1206-1224, 2017.

É. , C. De-verdière, and J. Erickson, Tightening Nonsimple Paths and Cycles on Surfaces, SIAM Journal on Computing, vol.39, pp.3784-3813, 2010.

E. Dahlhaus, D. S. Johnson, C. H. Papadimitriou, P. D. Seymour, and M. Yannakakis, The complexity of multiterminal cuts, SIAM Journal on Computing, vol.23, pp.864-894, 1994.

R. G. Downey and M. R. Fellows, Parameterized Complexity, 1999.

N. Garg, V. V. Vazirani, and M. Yannakakis, Primal-dual approximation algorithms for integral flow and multicut in trees, Algorithmica, vol.18, pp.3-20, 1997.

D. Golovin, V. Nagarajan, and M. Singh, Approximating the k-multicut problem, Proceedings SODA, pp.621-630, 2006.

D. Marx, A Tight Lower Bound for Planar Multiway Cut with Fixed Number of Terminals, Proceedings ICALP, pp.677-688, 2012.

D. Marx and I. Razgon, Fixed-Parameter Tractability of Multicut Parameterized by the Size of the Cutset, SIAM Journal on Computing, vol.43, pp.355-388, 2014.

M. Yannakakis, P. Kanellakis, S. Cosmadakis, and C. Papadimitriou, Cutting and partitioning a graph after a fixed pattern, Proceedings ICALP, vol.154, pp.712-722, 1983.