2026-09-08T02:21:20Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:26430 2026-09-05T19:43:18Z ddc:004 open_access

Connected Dominating Sets in Triangulations Bose, Prosenjit Dujmović, Vida Houdrouge, Hussein Morin, Pat Odak, Saeed connected domination triangulations planar graphs graph drawing collinear sets A dominating set of a graph G is connected if it induces a connected graph in G. For planar triangulations, it has been known since 1990 that every n-vertex triangulation admits a connected dominating set of size at most n/2 - 1, and no improvement to this bound was known for over three decades. We break this longstanding barrier by showing that every n-vertex triangulation has a connected dominating set of size at most 10n/21. Equivalently, every triangulation admits a spanning tree with at least 11n/21 leaves. Moreover, we present an algorithm that computes such a set in optimal linear time. Our result narrows the gap to the best known lower bound and has graph drawing applications, establishing a bound for one-bend free sets and improving the known bound for simultaneous planar embeddings. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Prosenjit Bose and Vida Dujmović and Hussein Houdrouge and Pat Morin and Saeed Odak 2026 Is Part Of LIPIcs, Volume 374, 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2026.41 urn:nbn:de:0030-drops-264300 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2026.41 eng https://creativecommons.org/licenses/by/4.0/legalcode