DROPS

Document

Track A: Algorithms, Complexity and Games

DOI: 10.4230/LIPIcs.ICALP.2026.41

Connected Dominating Sets in Triangulations

Authors: Prosenjit Bose, Vida Dujmović, Hussein Houdrouge, Pat Morin, and Saeed Odak

Published in: LIPIcs, Volume 374, 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)

Abstract

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.

Cite as

Prosenjit Bose, Vida Dujmović, Hussein Houdrouge, Pat Morin, and Saeed Odak. Connected Dominating Sets in Triangulations. In 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 374, pp. 41:1-41:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{bose_et_al:LIPIcs.ICALP.2026.41,
  author =	{Bose, Prosenjit and Dujmovi\'{c}, Vida and Houdrouge, Hussein and Morin, Pat and Odak, Saeed},
  title =	{{Connected Dominating Sets in Triangulations}},
  booktitle =	{53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)},
  pages =	{41:1--41:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-428-4},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{374},
  editor =	{Bhattacharya, Sayan and Nanongkai, Danupon and Benedikt, Michael and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2026.41},
  URN =		{urn:nbn:de:0030-drops-264300},
  doi =		{10.4230/LIPIcs.ICALP.2026.41},
  annote =	{Keywords: connected domination, triangulations, planar graphs, graph drawing, collinear sets}
}

Search Results

Documents authored by Houdrouge, Hussein

Connected Dominating Sets in Triangulations

Abstract

Cite as

Thanks for your feedback!

Could not send message