Published On Dec 7, 2023
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.
show more