Saeed Odak

activity

20242026

collaborators

9 papers

cs.CG2026

On 2-Layer k-Matching-Planar Graphs

Saeed Odak, Jonathan Rollin, Torben Scheele

A graph is $k$ -matching-planar if it admits a drawing in the plane such that, for every edge $e$ , the edges crossing $e$ contain no matching of size greater than $k$ . The class of…

cs.CG2026

Shifting is Optimal under Gap-ETH: A Lower Bound Framework for Geometric Approximation Schemes

Manuel CÃ¡ceres, SÃ¡ndor Kisfaludi-Bak, Saeed Odak

The shifting technique of Hochbaum and Maass [J.ACM'85] produces PTASes with the fastest known running times $n^{O (1/ ε^{d - 1})}$ for several $d$ -dimensional geometric prob…

cs.CG2026

Closest Pair Queries in Vertical Slabs and Tight Bounds on the Number of Possible Answers

Ahmad Biniaz, Prosenjit Bose, Chaeyoon Chung +6

Let $S$ be a set of $n$ points in $R^{d}$ , where $d \geq 2$ is a constant, and let $H_{1}, H_{2}, \dots, H_{m + 1}$ be a sequence of vertical hyperplanes that are sorted by their fi…

cs.CG2026

Gap-ETH-Tight Algorithms for Hyperbolic TSP and Steiner Tree

SÃ¡ndor Kisfaludi-Bak, Saeed Odak, Satyam Singh +1

We give an approximation scheme for the TSP in $d$ -dimensional hyperbolic space that has optimal dependence on $ε$ under Gap-ETH. For any fixed dimension $d \geq 2$ and fo…

cs.CG2025

Noncrossing Longest Paths and Cycles

Greg Aloupis, Ahmad Biniaz, Prosenjit Bose +7

Edge crossings in geometric graphs are sometimes undesirable as they could lead to unwanted situations such as collisions in motion planning and inconsistency in VLSI layout. Short…

cs.DM2025

On Separating Path and Tree Systems in Graphs

Ahmad Biniaz, Prosenjit Bose, Jean-Lou De Carufel +6

We explore the concept of separating systems of vertex sets of graphs. A separating system of a set $X$ is a collection of subsets of $X$ such that for any pair of distinct element…