Showing cs.DSShow all
3 papers · 1 filter
cs.DS2026
Using Ray-shooting Queries for Sublinear Algorithms for Dominating Sets in RDV Graphs
Therese Biedl, Prashant Gokhale
In this paper, we study the dominating set problem in \emph{RDV graphs}, a graph class that lies between interval graphs and chordal graphs and is defined as the \textbf{v}ertex-in…
cs.DS2025
Face-hitting dominating sets in planar graphs: Alternative proof and linear-time algorithm
Therese Biedl
In a recent paper, Francis, Illickan, Jose and Rajendraprasad showed that every -vertex plane graph has (under some natural restrictions) a vertex-partition into two sets $V…
cs.DS2024
Improved Outerplanarity Bounds for Planar Graphs
Therese Biedl, Debajyoti Mondal
In this paper, we study the outerplanarity of planar graphs, i.e., the number of times that we must (in a planar embedding that we can initially freely choose) remove the outerface…