## Abstract

We study the Steiner tree problem on map graphs, which substantially generalize planar graphs as they allow arbitrarily large cliques. We obtain a PTAS for Steiner tree on map graphs, which builds on the result for planar edge weighted instances of Borradaile et al. The Steiner tree problem on map graphs can be casted as a special case of the planar node-weighted Steiner tree problem, for which only a 2.4-approximation is known. We prove and use a contraction decomposition theorem for planar node weighted instances. This readily reduces the problem of finding a PTAS for planar node-weighted Steiner tree to finding a spanner, i. e., a constant-factor approximation containing a nearly optimum solution. Finally, we pin-point places where known techniques for constructing such spanner fail on node weighted instances and further progress requires new ideas.

Original language | English |
---|---|

Title of host publication | LATIN 2020 |

Subtitle of host publication | Theoretical Informatics - 14th Latin American Symposium 2021, Proceedings |

Editors | Yoshiharu Kohayakawa, Flávio Keidi Miyazawa |

Pages | 3-14 |

Number of pages | 12 |

DOIs | |

Publication status | Published - 2020 |

MoE publication type | A4 Article in a conference publication |

Event | Latin American Symposium on Theoretical Informatics - Sao Paulo, Brazil Duration: 5 Jan 2021 → 8 Jan 2021 Conference number: 14 |

### Publication series

Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|

Publisher | Springer |

Volume | 12118 LNCS |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### Conference

Conference | Latin American Symposium on Theoretical Informatics |
---|---|

Abbreviated title | LATIN |

Country | Brazil |

City | Sao Paulo |

Period | 05/01/2021 → 08/01/2021 |