### Point-set Embeddability

Let G be a planar graph with n vertices and let P be a set of n points in the plane. We say that G is

*point-set embeddable on*P if G admits a planar drawing such that each vertex is mapped to a point of P and each edges is drawn as a polyline between its end-vertices.Gritzman, Mohar, Pach, and Pollack show that given any set P of n points in general position and given a graph G with n vertices, G is point-set embeddable on P if and only if G is an outerplanar graph.

Kaufmann and Wiese show that given any set of n points P and any planar graph G with n vertices, G is point-set embeddable on P with at most two bends per edge. In the same paper, it is shown a non-hamiltonian graph G and a set P of collinear points for which two bends are necessary. Notice also that the fact that a non-hamiltonian graph is not point-set embeddable with at most one bend per edge on a set of collinear points is a consequence of the fact that a planar graph has a two-page book embedding if and only if it is sub-hamiltonian.

The following question is still open.

**Problem 1:**Let P be a set of n non-collinear points and let G be a planar graph with n vertices. Is G point-set embeddable on P with at most one bend per edge?

This question is also motivated by the fact that every planar graph has a planar drawing with at most one bend per edge such that the vertices are drawn as points of a convex curve.

### Approximating a Minimum Spanning Tree

A

*em minimum spanning tree*of a set P of points is a connected, straight-line drawing that has P as vertex set and minimizes the total edge length.The problem of testing whether a tree can be drawn as a Euclidean minimum spanning tree in the plane is essentially solved. Monma and Suri proved that each tree with maximum vertex degree at most five can be drawn as a minimum spanning tree of some set of vertices by providing a linear time (real RAM) algorithm. In the same paper it is shown that every tree having at least one vertex with degree greater than six is minimum weight forbidden. As for trees having maximum degree equal to six, Eades and Whitesides showed that it is NP-hard to decide whether such trees can be drawn as minimum spanning trees.

We would like to investigate how to draw trees that are not realizable as minimum spanning trees in such a way that the resulting drawing is a "good approximation" of a minimum spanning tree. Let Gamma be a straight-line drawing and let W(Gamma) be the sum of the lengths of the edges of Gamma. Let P be the set of vertices of Gamma, let MST(P) be a minimum spanning tree of P and let W(MST(P)) be the sum of the lengths of MST(P).

**Problem 2:**Let T be a tree having maximum vertex degree d (d > 5). Compute a straight-line drawing Gamma of T such that W(Gamma) <= f(d) W(MST(P)), where f(d) is a function of the maximum vertex degree of T and f(d) does not depend on the size of T.

*k*-locally Delaunay DrawabilityA

*k-Locally Delaunay Graph*of a set S of points is a geometric graph Gamma such that for every edge (u,v) of Gamma there exists a disk D(u,v) such that: (1) D(u,v) is a closed set; (2) D(u,v) contains edge (u,v); (3) D(u,v) can contain a vertex w of Gamma different from u and v only if the graph theoretic distance of w from u and from v is larger than k (that is, there are more than k hops in Gamma from u to w and from u to w).We would like to characterize families of graphs that can be drawn as k-locally Delaunay graphs for different values of k. If one focuses on (subclasses of) planar graphs, then the value k=2 seems to be of particular interest: We say that a planar graph G is D_2-drawable if G has a straight-line drawing that is the 2-locally Delaunay graph of the set of its vertices. Namely, Pinchasi and Smorodinsky proved that D_2-drawable graphs have a linear number of edges. A consequence of existing literature is that not all planar graphs are D_2-drawable and that all connected outerplanar graphs are D_2-drawable.

**Problem 3:**Which planar graphs are D_2-drawable graphs. A starting point could be to look at subfamilies of the planar graphs, for example two-terminal series -parallel graphs.