Ahmad Biniaz

activity

20122026

most citedToken Swapping on Trees

8 citations · 24 across the 27 of their papers we have counts for

collaborators

43 papers

cs.DS2026

Minimum Sum Vertex Cover via Minimum Vertex Cover

Ahmad Biniaz, Jean-Lou De Carufel, Anil Maheshwari +2

The Minimum Sum Vertex Cover (MSVC) problem asks for an ordering of the vertices of a graph that minimizes the sum, over all edges, of the time at which each edge is first covered.…

cs.CG2025

An Improved Bound for Plane Covering Paths

Hugo A. Akitaya, Greg Aloupis, Ahmad Biniaz +8

A covering path for a finite set $P$ of points in the plane is a polygonal path such that every point of $P$ lies on a segment of the path. The vertices of the path need not be at…

cs.CG2025

Polychromatic Coloring of Tuples in Hypergraphs

Ahmad Biniaz, Jean-Lou De Carufel, Anil Maheshwari +3

A hypergraph $H$ consists of a set $V$ of vertices and a set $E$ of hyperedges that are subsets of $V$ . A $t$ -tuple of $H$ is a subset of $t$ vertices of $V$ . A $t$ -tuple $k$ -color…

cs.CG2025

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.CG2024

Contiguous Boundary Guarding

Ahmad Biniaz, Anil Maheshwari, Joseph S. B. Mitchell +3

We study the problem of guarding the boundary of a simple polygon with a minimum number of guards such that each guard covers a contiguous portion of the boundary. First, we presen…

cs.CG2024

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.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…

cs.CG2024

Euclidean Maximum Matchings in the Plane---Local to Global

Ahmad Biniaz, Anil Maheshwari, Michiel Smid

Let $M$ be a perfect matching on a set of points in the plane where every edge is a line segment between two points. We say that $M$ is globally maximum if it is a maximum-length m…

cs.CG2024

Metric and Geometric Spanners that are Resilient to Degree-Bounded Edge Faults

Ahmad Biniaz, Jean-Lou De Carufel, Anil Maheshwari +1

Let $H$ be an edge-weighted graph, and let $G$ be a subgraph of $H$ . We say that $G$ is an $f$ -fault-tolerant $t$ -spanner for $H$ , if the following is true for any subset $F$ of at…

cs.DM2023★ 1 cited

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…

cs.CG2023

Improved Bounds for Covering Paths and Trees in the Plane

Ahmad Biniaz

A covering path for a planar point set is a path drawn in the plane with straight-line edges such that every point lies at a vertex or on an edge of the path. A covering tree is de…

cs.CG2021

Acute Tours in the Plane

Ahmad Biniaz

We confirm the following conjecture of Fekete and Woeginger from 1997: for any sufficiently large even number $n$ , every set of $n$ points in the plane can be connected by a spanni…

cs.CG2021

Approximating bottleneck spanning trees on partitioned tuples of points

Ahmad Biniaz, Anil Maheshwari, Michiel Smid

We present approximation algorithms for the following NP-hard optimization problems related to bottleneck spanning trees in metric spaces. 1. The disjoint bottleneck spanning tree…

cs.CG2020

Improved approximation ratios for two Euclidean maximum spanning tree problems

Ahmad Biniaz

We study the following two maximization problems related to spanning trees in the Euclidean plane. It is not known whether or not these problems are NP-hard. We present approximati…

math.CO2020

A short proof of the non-biplanarity of $K_{9}$

Ahmad Biniaz

Battle, Harary, and Kodama (1962) and independently Tutte (1963) proved that the complete graph with nine vertices is not biplanar. Aiming towards simplicity and brevity, in this n…

cs.DS2020

Better approximation algorithms for maximum weight internal spanning trees in cubic graphs and claw-free graphs

Ahmad Biniaz

Given a connected vertex-weighted graph $G$ , the maximum weight internal spanning tree (MaxwIST) problem asks for a spanning tree of $G$ that maximizes the total weight of internal…

cs.CG2020★ 1 cited

Compatible Paths on Labelled Point Sets

Elena Arseneva, Yeganeh Bahoo, Ahmad Biniaz +8

Let $P$ and $Q$ be finite point sets of the same cardinality in $R^{2}$ , each labelled from $1$ to $n$ . Two noncrossing geometric graphs $G_{P}$ and $G_{Q}$ spanning $P$ and $Q$ …

cs.CG2019

Euclidean Bottleneck Bounded-Degree Spanning Tree Ratios

Ahmad Biniaz

Inspired by the seminal works of Khuller et al. (STOC 1994) and Chan (SoCG 2003) we study the bottleneck version of the Euclidean bounded-degree spanning tree problem. A bottleneck…

cs.CG2019

A Short Proof of the Toughness of Delaunay Triangulations

Ahmad Biniaz

We present a self-contained short proof of the seminal result of Dillencourt (SoCG 1987 and DCG 1990) that Delaunay triangulations, of planar point sets in general position, are 1-…

cs.CG2019

Packing Boundary-Anchored Rectangles and Squares

Therese Biedl, Ahmad Biniaz, Anil Maheshwari +1

Consider a set $P$ of $n$ points on the boundary of an axis-aligned square $Q$ . We study the boundary-anchored packing problem on $P$ in which the goal is to find a set of interior…

cs.CG2019

Flip Distance to some Plane Configurations

Ahmad Biniaz, Anil Maheshwari, Michiel Smid

We study an old geometric optimization problem in the plane. Given a perfect matching $M$ on a set of $n$ points in the plane, we can transform it to a non-crossing perfect matchin…

cs.CG2019

Minimum Ply Covering of Points with Disks and Squares

Therese Biedl, Ahmad Biniaz, Anna Lubiw

Following the seminal work of Erlebach and van Leeuwen in SODA 2008, we introduce the minimum ply covering problem. Given a set $P$ of points and a set $S$ of geometric objects, bo…

cs.CC2019★ 8 cited

Token Swapping on Trees

Ahmad Biniaz, Kshitij Jain, Anna Lubiw +6

The input to the token swapping problem is a graph with vertices $v_{1}, v_{2}, \dots, v_{n}$ , and $n$ tokens with labels $1, 2, \dots, n$ , one on each vertex. The goal is to get token…

cs.CG2019

Plane Hop Spanners for Unit Disk Graphs: Simpler and Better

Ahmad Biniaz

The unit disk graph (UDG) is a widely employed model for the study of wireless networks. In this model, wireless nodes are represented by points in the plane and there is an edge b…

Minimum Sum Vertex Cover via Minimum Vertex Cover

An Improved Bound for Plane Covering Paths

Polychromatic Coloring of Tuples in Hypergraphs

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

Contiguous Boundary Guarding

Noncrossing Longest Paths and Cycles

Minimum Plane Bichromatic Spanning Trees

Euclidean Maximum Matchings in the Plane---Local to Global

Metric and Geometric Spanners that are Resilient to Degree-Bounded Edge Faults

On Separating Path and Tree Systems in Graphs

Improved Bounds for Covering Paths and Trees in the Plane

Acute Tours in the Plane

Approximating bottleneck spanning trees on partitioned tuples of points

Improved approximation ratios for two Euclidean maximum spanning tree problems

A short proof of the non-biplanarity of K9​

Better approximation algorithms for maximum weight internal spanning trees in cubic graphs and claw-free graphs

Compatible Paths on Labelled Point Sets

Euclidean Bottleneck Bounded-Degree Spanning Tree Ratios

A Short Proof of the Toughness of Delaunay Triangulations

Packing Boundary-Anchored Rectangles and Squares

Flip Distance to some Plane Configurations

Minimum Ply Covering of Points with Disks and Squares

Token Swapping on Trees

Plane Hop Spanners for Unit Disk Graphs: Simpler and Better

A short proof of the non-biplanarity of $K_{9}$