6 papers
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 sim…
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…
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…
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…
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…
Finding maximum matchings in RDV graphs efficiently
Therese Biedl, Prashant Gokhale
In this paper, we study the maximum matching problem in RDV graphs, i.e., graphs that are vertex-intersection graphs of downward paths in a rooted tree. We show that this problem c…