3 papers
cs.CG2024
Spanners in Planar Domains via Steiner Spanners and non-Steiner Tree Covers
Sujoy Bhore, Balázs Keszegh, Andrey Kupavskii +4
We study spanners in planar domains, including polygonal domains, polyhedral terrain, and planar metrics. Previous work showed that for any constant , one could constru…
cs.DM2023
Plane Multigraphs with One-Bend and Circular-Arc Edges of a Fixed Angle
Csaba D. Tóth
For an angle , we consider plane graphs and multigraphs in which the edges are either (i) one-bend polylines with an angle between the two edge segments, or (ii) ci…
cs.DS2023
Online Duet between Metric Embeddings and Minimum-Weight Perfect Matchings
Sujoy Bhore, Arnold Filtser, Csaba D. Tóth
Low-distortional metric embeddings are a crucial component in the modern algorithmic toolkit. In an online metric embedding, points arrive sequentially and the goal is to embed the…