
Improved approximation ratios for two Euclidean maximum spanning tree problems
We study the following two maximization problems related to spanning tre...
read it

A short proof of the nonbiplanarity of K_9
Battle, Harary, and Kodama (1962) and independently Tutte (1963) proved ...
read it

Better approximation algorithms for maximum weight internal spanning trees in cubic graphs and clawfree graphs
Given a connected vertexweighted graph G, the maximum weight internal s...
read it

Compatible Paths on Labelled Point Sets
Let P and Q be finite point sets of the same cardinality in ℝ^2, each la...
read it

Euclidean Bottleneck BoundedDegree Spanning Tree Ratios
Inspired by the seminal works of Khuller et al. (STOC 1994) and Chan (So...
read it

A Short Proof of the Toughness of Delaunay Triangulations
We present a selfcontained short proof of the seminal result of Dillenc...
read it

Packing BoundaryAnchored Rectangles and Squares
Consider a set P of n points on the boundary of an axisaligned square Q...
read it

Flip Distance to some Plane Configurations
We study an old geometric optimization problem in the plane. Given a per...
read it

Minimum Ply Covering of Points with Disks and Squares
Following the seminal work of Erlebach and van Leeuwen in SODA 2008, we ...
read it

Token Swapping on Trees
The input to the token swapping problem is a graph with vertices v_1, v_...
read it

Plane Hop Spanners for Unit Disk Graphs: Simpler and Better
The unit disk graph (UDG) is a widely employed model for the study of wi...
read it

Maximum Matchings and Minimum Blocking Sets in Θ_6Graphs
Θ_6Graphs are important geometric graphs that have many applications es...
read it

Stabbing Pairwise Intersecting Disks by Four Points
Following the seminal works of Danzer (1956, 1986) and Stachó (1965,1981...
read it

On the Minimum Consistent Subset Problem
Let P be a set of n colored points in the plane. Introduced by Hart (196...
read it

Plane and Planarity Thresholds for Random Geometric Graphs
A random geometric graph, G(n,r), is formed by choosing n points indepen...
read it

Improved Bounds for Guarding Plane Graphs with Edges
An "edge guard set" of a plane graph G is a subset Γ of edges of G such ...
read it

Packing Plane Spanning Trees into a Point Set
Let P be a set of n points in the plane in general position. We show tha...
read it

Faster Algorithms for some Optimization Problems on Collinear Points
We propose faster algorithms for the following three optimization proble...
read it

Rollercoasters and Caterpillars
A rollercoaster is a sequence of real numbers for which every maximal co...
read it

Compatible 4Holes in Point Sets
Counting interiordisjoint empty convex polygons in a point set is a typ...
read it
Ahmad Biniaz
is this you? claim profile