Title: Connected Dominating Sets in Triangulations (with Applications)

Speaker: Vida Dujmović, University of Ottawa

Date and time: 2pm (New York time), Tuesday, December 5, 2023

Place: On Zoom (details provided on the seminar mailing list)

We show that every $n$-vertex triangulation has a connected dominating set of size at most $10n/21$. Equivalently, every $n$ vertex triangulation has a spanning tree with at least $11n/21$ leaves. Prior to the current work, the best known bounds were $2n/3$ and $n/3$, respectively. As an application of this, we show that every $n$-vertex planar graph has a one-bend non-crossing drawing in which some set of at least $11n/21$ vertices is drawn on the $x$-axis.