4 papers
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…
Bipartite Graphs Are Not Well-Quasi-Ordered by Bipartite Minors
Therese Biedl, Dinis Vitorino
In "Bipartite minors" [Journal of Combinatorial Theory, Series B, 2016], Chudnovsky et al. introduced the bipartite minor relation, a quasi-order on the class of bipartite graphs s…
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…
Computing Conforming Partitions with Low Stabbing Number for Rectilinear Polygons
Therese Biedl, Stephane Durocher, Debajyoti Mondal +2
A conforming partition of a rectilinear n-gon P (possibly with holes) is a partition of P into rectangles without using Steiner points (i.e., all corners of all rectangles must lie…