Source author record

Ahmad Biniaz

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Computational Geometry Discrete Mathematics Data Structures and Algorithms

Catalog footprint

Research overview

14works

3topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2025arXiv

Noncrossing Longest Paths and Cycles

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 geometric structures such as shortest perfect matchings, shortest spanning trees, shortest spanning paths, and shortest spanning cycles on a given point set are inherently noncrossing. However, the longest such structures need not be noncrossing. In fact, it is intuitive to expect many edge crossings in various geometric graphs that are longest. Recently, Álvarez-Rebollar, Cravioto-Lagos, Marín, Solé-Pi, and Urrutia (Graphs and Combinatorics, 2024) constructed a set of points for which the longest perfect matching is noncrossing. They raised several challenging questions in this direction. In particular, they asked whether the longest spanning path, on any finite set of points in the plane, must have a pair of crossing edges. They also conjectured that the longest spanning cycle must have a pair of crossing edges. In this paper, we give a negative answer to the question and also refute the conjecture. We present a framework for constructing arbitrarily large point sets for which the longest perfect matchings, the longest spanning paths, and the longest spanning cycles are noncrossing.

preprint2022arXiv

Acute Tours in the Plane

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 spanning tour (Hamiltonian cycle) consisting of straight-line edges such that the angle between any two consecutive edges is at most $π/2$ . Our proof is constructive and suggests a simple $O(n\log n)$ -time algorithm for finding such a tour. The previous best-known upper bound on the angle is $2π/3$ , and it is due to Dumitrescu, Pach and Tóth (2009).

preprint2020arXiv

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

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 nodes. This problem is NP-hard and APX-hard, with the currently best known approximation factor $1/2$ (Chen et al., Algorithmica 2019). For the case of claw-free graphs, Chen et al. present an involved approximation algorithm with approximation factor $7/12$ . They asked whether it is possible to improve these ratios, in particular for claw-free graphs and cubic graphs. We improve the approximation factors for the MaxwIST problem in cubic graphs and claw-free graphs. For cubic graphs we present an algorithm that computes a spanning tree whose total weight of internal vertices is at least $\frac{3}{4}-\frac{3}{n}$ times the total weight of all vertices, where $n$ is the number of vertices of $G$ . This ratio is almost tight for large values of $n$ . For claw-free graphs of degree at least three, we present an algorithm that computes a spanning tree whose total internal weight is at least $\frac{3}{5}-\frac{1}{n}$ times the total vertex weight. The degree constraint is necessary as this ratio may not be achievable if we allow vertices of degree less than three. With the above ratios, we immediately obtain better approximation algorithms with factors $\frac{3}{4}-ε$ and $\frac{3}{5}-ε$ for the MaxwIST problem in cubic graphs and claw-free graphs of degree at least three, for any $ε>0$ . In addition to improving the approximation factors, the new algorithms are relatively short compared to that of Chen et al.. The new algorithms are fairly simple, and employ a variant of the depth-first search algorithm that selects a relatively-large-weight vertex in every branching step. Moreover, the new algorithms take linear time while previous algorithms for similar problem instances are super-linear.

preprint2020arXiv

Compatible Paths on Labelled Point Sets

Let $P$ and $Q$ be finite point sets of the same cardinality in $\mathbb{R}^2$ , each labelled from $1$ to $n$ . Two noncrossing geometric graphs $G_P$ and $G_Q$ spanning $P$ and $Q$ , respectively, are called compatible if for every face $f$ in $G_P$ , there exists a corresponding face in $G_Q$ with the same clockwise ordering of the vertices on its boundary as in $f$ . In particular, $G_P$ and $G_Q$ must be straight-line embeddings of the same connected $n$ -vertex graph. Deciding whether two labelled point sets admit compatible geometric paths is known to be NP-complete. We give polynomial-time algorithms to find compatible paths or report that none exist in three scenarios: $O(n)$ time for points in convex position; $O(n^2)$ time for two simple polygons, where the paths are restricted to remain inside the closed polygons; and $O(n^2 \log n)$ time for points in general position if the paths are restricted to be monotone.

preprint2016arXiv

Matchings in Geometric Graphs

A geometric graph is a graph whose vertex set is a set of points in the plane and whose edge set contains straight-line segments. A matching in a graph is a subset of edges of the graph with no shared vertices. A matching is called perfect if it matches all the vertices of the underling graph. A geometric matching is a matching in a geometric graph. In this thesis, we study matching problems in various geometric graphs. Among the family of geometric graphs we look at complete graphs, complete bipartite graphs, complete multipartite graphs, Delaunay graphs, Gabriel graphs, and $Θ$ -graphs. The classical matching problem is to find a matching of maximum size in a given graph. We study this problem as well as some of its variants on geometric graphs. The bottleneck matching problem is to find a maximum matching that minimizes the length of the longest edge. The plane matching problem is to find a maximum matching so that the edges in the matching are pairwise non-crossing. A geometric matching is strong with respect to a given shape $S$ if we can assign to each edge in the matching a scaled version of $S$ such that the shapes representing the edges are pairwise disjoint. The strong matching problem is to find a maximum strong matching with respect to a given shape. The matching packing problem is to pack as many edge-disjoint perfect matchings as possible into a geometric graph. We study these problems and establish lower and upper bounds on the size of different kinds of matchings in various geometric graphs. We also present algorithms for computing such matchings. Some of the presented bounds are tight, while the others need to be sharpened.

preprint2016arXiv

Spanning Trees in Multipartite Geometric Graphs

Let $R$ and $B$ be two disjoint sets of points in the plane where the points of $R$ are colored red and the points of $B$ are colored blue, and let $n=|R\cup B|$ . A bichromatic spanning tree is a spanning tree in the complete bipartite geometric graph with bipartition $(R,B)$ . The minimum (respectively maximum) bichromatic spanning tree problem is the problem of computing a bichromatic spanning tree of minimum (respectively maximum) total edge length. 1. We present a simple algorithm that solves the minimum bichromatic spanning tree problem in $O(n\log^3 n)$ time. This algorithm can easily be extended to solve the maximum bichromatic spanning tree problem within the same time bound. It also can easily be generalized to multicolored point sets. 2. We present $Θ(n\log n)$ -time algorithms that solve the minimum and the maximum bichromatic spanning tree problems. 3. We extend the bichromatic spanning tree algorithms and solve the multicolored version of these problems in $O(n\log n\log k)$ time, where $k$ is the number of different colors (or the size of the multipartition in a complete multipartite geometric graph).

preprint2015arXiv

Approximating the Bottleneck Plane Perfect Matching of a Point Set

A bottleneck plane perfect matching of a set of $n$ points in $\mathbb{R}^2$ is defined to be a perfect non-crossing matching that minimizes the length of the longest edge; the length of this longest edge is known as {\em bottleneck}. The problem of computing a bottleneck plane perfect matching has been proved to be NP-hard. We present an algorithm that computes a bottleneck plane matching of size at least $\frac{n}{5}$ in $O(n \log^2 n)$ -time. Then we extend our idea toward an $O(n\log n)$ -time approximation algorithm which computes a plane matching of size at least $\frac{2n}{5}$ whose edges have length at most $\sqrt{2}+\sqrt{3}$ times the bottleneck.

preprint2015arXiv

Packing Plane Perfect Matchings into a Point Set

Given a set $P$ of $n$ points in the plane, where $n$ is even, we consider the following question: How many plane perfect matchings can be packed into $P$ ? We prove that at least $\lceil\log_2{n}\rceil-2$ plane perfect matchings can be packed into any point set $P$ . For some special configurations of point sets, we give the exact answer. We also consider some extensions of this problem.

preprint2015arXiv

Plane Bichromatic Trees of Low Degree

Let $R$ and $B$ be two disjoint sets of points in the plane such that $|B|\leqslant |R|$ , and no three points of $R\cup B$ are collinear. We show that the geometric complete bipartite graph $K(R,B)$ contains a non-crossing spanning tree whose maximum degree is at most $\max\left\{3, \left\lceil \frac{|R|-1}{|B|}\right\rceil + 1\right\}$ ; this is the best possible upper bound on the maximum degree. This solves an open problem posed by Abellanas et al. at the Graph Drawing Symposium, 1996.

preprint2015arXiv

Strong Matching of Points with Geometric Shapes

Let $P$ be a set of $n$ points in general position in the plane. Given a convex geometric shape $S$ , a geometric graph $G_S(P)$ on $P$ is defined to have an edge between two points if and only if there exists an empty homothet of $S$ having the two points on its boundary. A matching in $G_S(P)$ is said to be $strong$ , if the homothests of $S$ representing the edges of the matching, are pairwise disjoint, i.e., do not share any point in the plane. We consider the problem of computing a strong matching in $G_S(P)$ , where $S$ is a diametral-disk, an equilateral-triangle, or a square. We present an algorithm which computes a strong matching in $G_S(P)$ ; if $S$ is a diametral-disk, then it computes a strong matching of size at least $\lceil \frac{n-1}{17} \rceil$ , and if $S$ is an equilateral-triangle, then it computes a strong matching of size at least $\lceil \frac{n-1}{9} \rceil$ . If $S$ can be a downward or an upward equilateral-triangle, we compute a strong matching of size at least $\lceil \frac{n-1}{4} \rceil$ in $G_S(P)$ . When $S$ is an axis-aligned square we compute a strong matching of size $\lceil \frac{n-1}{4} \rceil$ in $G_S(P)$ , which improves the previous lower bound of $\lceil \frac{n}{5} \rceil$ .

preprint2014arXiv

Higher-Order Triangular-Distance Delaunay Graphs: Graph-Theoretical Properties

We consider an extension of the triangular-distance Delaunay graphs (TD-Delaunay) on a set $P$ of points in the plane. In TD-Delaunay, the convex distance is defined by a fixed-oriented equilateral triangle $\triangledown$ , and there is an edge between two points in $P$ if and only if there is an empty homothet of $\triangledown$ having the two points on its boundary. We consider higher-order triangular-distance Delaunay graphs, namely $k$ -TD, which contains an edge between two points if the interior of the homothet of $\triangledown$ having the two points on its boundary contains at most $k$ points of $P$ . We consider the connectivity, Hamiltonicity and perfect-matching admissibility of $k$ -TD. Finally we consider the problem of blocking the edges of $k$ -TD.

preprint2014arXiv

Matching in Gabriel Graphs

Given a set $P$ of $n$ points in the plane, the order- $k$ Gabriel graph on $P$ , denoted by $k$ - $GG$ , has an edge between two points $p$ and $q$ if and only if the closed disk with diameter $pq$ contains at most $k$ points of $P$ , excluding $p$ and $q$ . We study matching problems in $k$ - $GG$ graphs. We show that a Euclidean bottleneck perfect matching of $P$ is contained in $10$ - $GG$ , but $8$ - $GG$ may not have any Euclidean bottleneck perfect matching. In addition we show that $0$ - $GG$ has a matching of size at least $\frac{n-1}{4}$ and this bound is tight. We also prove that $1$ - $GG$ has a matching of size at least $\frac{2(n-1)}{5}$ and $2$ - $GG$ has a perfect matching. Finally we consider the problem of blocking the edges of $k$ - $GG$ .

preprint2013arXiv

An Optimal Algorithm for the Euclidean Bottleneck Full Steiner Tree Problem

Let $P$ and $S$ be two disjoint sets of $n$ and $m$ points in the plane, respectively. We consider the problem of computing a Steiner tree whose Steiner vertices belong to $S$ , in which each point of $P$ is a leaf, and whose longest edge length is minimum. We present an algorithm that computes such a tree in $O((n+m)\log m)$ time, improving the previously best result by a logarithmic factor. We also prove a matching lower bound in the algebraic computation tree model.

preprint2012arXiv

Fixed-Orientation Equilateral Triangle Matching of Point Sets

Given a point set $P$ and a class $\mathcal{C}$ of geometric objects, $G_\mathcal{C}(P)$ is a geometric graph with vertex set $P$ such that any two vertices $p$ and $q$ are adjacent if and only if there is some $C \in \mathcal{C}$ containing both $p$ and $q$ but no other points from $P$ . We study $G_{\bigtriangledown}(P)$ graphs where $\bigtriangledown$ is the class of downward equilateral triangles (ie. equilateral triangles with one of their sides parallel to the x-axis and the corner opposite to this side below that side). For point sets in general position, these graphs have been shown to be equivalent to half- $Θ_6$ graphs and TD-Delaunay graphs. The main result in our paper is that for point sets $P$ in general position, $G_{\bigtriangledown}(P)$ always contains a matching of size at least $\lceil\frac{n-2}{3}\rceil$ and this bound cannot be improved above $\lceil\frac{n-1}{3}\rceil$ . We also give some structural properties of $G_{\davidsstar}(P)$ graphs, where $\davidsstar$ is the class which contains both upward and downward equilateral triangles. We show that for point sets in general position, the block cut point graph of $G_{\davidsstar}(P)$ is simply a path. Through the equivalence of $G_{\davidsstar}(P)$ graphs with $Θ_6$ graphs, we also derive that any $Θ_6$ graph can have at most $5n-11$ edges, for point sets in general position.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Ahmad Biniaz

Research overview

Is this your work?

14 publications

Noncrossing Longest Paths and Cycles

Acute Tours in the Plane

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

Compatible Paths on Labelled Point Sets

Matchings in Geometric Graphs

Spanning Trees in Multipartite Geometric Graphs

Approximating the Bottleneck Plane Perfect Matching of a Point Set

Packing Plane Perfect Matchings into a Point Set

Plane Bichromatic Trees of Low Degree

Strong Matching of Points with Geometric Shapes

Higher-Order Triangular-Distance Delaunay Graphs: Graph-Theoretical Properties

Matching in Gabriel Graphs

An Optimal Algorithm for the Euclidean Bottleneck Full Steiner Tree Problem

Fixed-Orientation Equilateral Triangle Matching of Point Sets

See the researcher in context

Building this map preview