Showing cs.CGShow all
3 papers · 1 filter
cs.CG2025
The Price of Connectivity Augmentation on Planar Graphs
Hugo A. Akitaya, Justin Dallant, Erik D. Demaine +5
Given two classes of graphs, , and a -connected graph , we wish to augment with a smallest cardinality set of new e…
cs.CG2025
An Improved Bound for Plane Covering Paths
Hugo A. Akitaya, Greg Aloupis, Ahmad Biniaz +8
A covering path for a finite set of points in the plane is a polygonal path such that every point of lies on a segment of the path. The vertices of the path need not be at…
cs.CG2024
Minimum Plane Bichromatic Spanning Trees
Hugo A. Akitaya, Ahmad Biniaz, Erik D. Demaine +3
For a set of red and blue points in the plane, a minimum bichromatic spanning tree (MinBST) is a shortest spanning tree of the points such that every edge has a red and a blue endp…