Author(s): | Cohen-Addad, Vincent; de Mesmay, Arnaud |

Title: | A fixed parameter tractable approximation scheme for the optimal cut graph of a surface |

Title Series: | LNCS |

Affiliation | IST Austria |

Abstract: | Given a graph G cellularly embedded on a surface Σ of genus g, a cut graph is a subgraph of G such that cutting Σ along G yields a topological disk. We provide a fixed parameter tractable approximation scheme for the problem of computing the shortest cut graph, that is, for any ε > 0, we show how to compute a (1 + ε) approximation of the shortest cut graph in time f(ε, g)n3. Our techniques first rely on the computation of a spanner for the problem using the technique of brick decompositions, to reduce the problem to the case of bounded tree-width. Then, to solve the bounded tree-width case, we introduce a variant of the surface-cut decomposition of Rué, Sau and Thilikos, which may be of independent interest. |

Conference Title: | ESA: European Symposium on Algorithms |

Volume: | 9294 |

Conference Dates: | September 14-16, 2015 |

Conference Location: | Patras, Greece |

ISBN: | 9783662483497 |

Publisher: | Springer |

Date Published: | 2015-09-01 |

Start Page: | 386 |

End Page: | 398 |

URL: | |

DOI: | 10.1007/978-3-662-48350-3 |

Notes: | The research of the first author was partially supported by ANR RDAM. The research of the second author leading to these results has received funding from the People Programme (Marie Curie Actions) of the European Union’s Seventh Framework Programme (FP7/2007-2013) under REA grant agreement n◦ [291734]. |

Open access: | yes (repository) |

IST Austria Authors

Related IST Austria Work