Showing 2024Show all
3 papers · 1 filter
cs.CG2024
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…
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…
cs.CG2024
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…