Planar embedding of trees on point sets without the general position assumption

Authors : Asghar Asgharian Sardroud, Alireza Bagheri

Pages : 820-829

View : 11 | Download : 8

Publication Date : 9999-12-31

Article Type : Makaleler

Abstract :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.
Keywords : Point-set embedding, tree embedding, general position assumption, graph drawing, minimum bend embedding