-
Article
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) consisti...
-
Chapter and Conference Paper
Piercing Pairwise Intersecting Convex Shapes in the Plane
Let C be any family of pairwise intersecting convex shapes in a two dimensional Euclidean space. Let \(\tau (C)\) ...
-
Article
Bounded-Angle Minimum Spanning Trees
Motivated by the connectivity problem in wireless networks with directional antennas, we study bounded-angle spanning trees. Let P be a set of points in the plane and let
-
Article
Euclidean Bottleneck Bounded-Degree Spanning Tree Ratios
Inspired by the seminal works of Khuller et al. (SIAM J. Comput. 25(2), 355–368 (1996)) and Chan (Discrete Comput. Geom. 32(2), 177–194 (2004)) we study the bottleneck version of the Euclidean bounded-degree span...
-
Article
On the Minimum Consistent Subset Problem
Let P be a set of n colored points in the d-dimensional Euclidean space. Introduced by Hart (1968), a consistent subset of P, is a set $$S\sub...
-
Chapter and Conference Paper
A Short Proof of the Non-biplanarity of \(K_9\)
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 note we provide a short proof ...
-
Chapter and Conference Paper
On the Spanning and Routing Ratios of the Directed \(\varTheta _6\) -Graph
The family of \(\varTheta _k\) Θ k ...
-
Chapter and Conference Paper
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 ...
-
Chapter and Conference Paper
Euclidean Maximum Matchings in the Plane—Local to Global
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 matching on all points. We say that M
-
Chapter and Conference Paper
The Minimum Moving Spanning Tree Problem
We investigate the problem of finding a spanning tree of a set of moving points in the plane that minimizes the maximum total weight (sum of Euclidean distances between edge endpoints) or the maximum bottlenec...
-
Article
Maximum Plane Trees in Multipartite Geometric Graphs
A geometric graph is a graph whose vertices are points in the plane and whose edges are straight-line segments between the points. A plane spanning tree in a geometric graph is a spanning tree that is non-cros...
-
Article
Improved Bounds for Guarding Plane Graphs with Edges
An edge guard set of a plane graph G is a subset \(\varGamma \) Γ ...
-
Chapter and Conference Paper
Maximum Matchings and Minimum Blocking Sets in \(\varTheta _6\) -Graphs
\(\varTheta _6\) -graphs are important geometric graphs that have many applications especially in wireless sensor netw...
-
Chapter and Conference Paper
On the Minimum Consistent Subset Problem
Let P be a set of n colored points in the plane. Introduced by Hart [7], a consistent subset of P, is a set \(S\subseteq P\) ...
-
Chapter and Conference Paper
Plane Hop Spanners for Unit Disk Graphs
The unit disk graph (UDG) is a widely employed model for the study of wireless networks
-
Article
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 ...
-
Article
Plane Bichromatic Trees of Low Degree
Let R and B be two disjoint sets of points in the plane such that \(|B|\le |R|\) ...
-
Chapter and Conference Paper
Maximum Plane Trees in Multipartite Geometric Graphs
A geometric graph is a graph whose vertices are points in the plane and whose edges are straight-line segments between the points. A plane spanning tree in a geometric graph is a spanning tree that is non-cros...
-
Chapter and Conference Paper
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 ...
-
Chapter and Conference Paper
Plane Geodesic Spanning Trees, Hamiltonian Cycles, and Perfect Matchings in a Simple Polygon
Let S be a finite set of points in the interior of a simple polygon P. A geodesic graph, \(G_P(S,E)\) ...
