Let G = (V, E) be a graph with n vertices and let P be a set of n points in the plane. We show that deciding whether there is a planar straight-line embedding of G such that the vertices V are embedded onto the points P is ...

A Manhattan p–q path is a geodesic in the Manhattan (or L1-) metric that connects p and q, i.e. a staircase path between p and q. Given a set of points P in the plane, a Manhattan network is a set of axis-parallel line ...

In this paper we deal with two types of graph convexities, which are the most natural path convexities in a graph and which are defined by a system P of paths in a connected graph G: the geodesic convexity (also called ...

We consider subdivisions of convex bodies G in two subsets E and G\E. We obtain several inequalities comparing the relative volume 1) with the minimum relative diameter and 2) with the maximum relative diameter. In the ...

Problem 50 in the Open Problems Project asks whether any triangulation on a point set in the plane contains a pointed spanning tree as a subgraph. We provide a counterexample. As a consequence we show that there ...

Let P be a simple polygon. We de ne a witness set W to be a set of points su h that if any (prospective) guard set G guards W, then it is guaranteed that G guards P . We show that not all polygons admit a nite witness ...

We present a simple dynamic programming based method for counting straight-edge triangulations of planar point sets. This method can be adapted to solve related problems such as nding the best triangulation of a point set ...

Fencing problems deal with the bisection of a convex body in a way that some geometric measures are optimized. We study bisections of planar bounded convex sets by straight line cuts and also bisections by hyperplane cuts ...

We consider the problem of computing large connected regions in a triangulated terrain of size n for which the normals of the triangles deviate by at most some small fixed angle. In previous work an exact near-quadratic ...

Three different concepts of depth in a point set are considered and compared: Convex depth, location depth and Delaunay depth. As a notion of weight is naturally associated to each depth definition, we also present results ...