Turkish Journal of Mathematics




The problem of point-set embedding of a planar graph $G$ on a point set $P$ in the plane is defined as finding a straight-line planar drawing of $G$ such that the nodes of $G$ are mapped one to one on the points of $P$. Previous works in this area mostly assume that the points of $P$ are in general position, i.e. $P$ does not contain any three collinear points. However, in most of the real applications we cannot assume the general position assumption. In this paper, we show that deciding the point-set embeddability of trees without the general position assumption is NP-complete. Then we introduce an algorithm for point-set embedding of $n$-node binary trees with at most $\frac{n}{3}$ total bends on any point set. We also give some results when the problem is limited to degree-constrained trees and point sets having constant number of collinear points.

First Page


Last Page


Included in

Mathematics Commons