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.
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.
A 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.