Vida Dujmović: Connected Dominating Sets in Triangulations (with Applications)
Computational Geometry Computational Geometry
594 subscribers
103 views
3

 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

Share/Embed