Turkish Journal of Mathematics
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.
DOI
10.3906/mat-1410-12
Keywords
Point-set embedding, tree embedding, general position assumption, graph drawing, minimum bend embedding
First Page
820
Last Page
829
Recommended Citation
SARDROUD, ASGHAR ASGHARIAN and BAGHERI, ALIREZA
(2015)
"Planar embedding of trees on point sets without the general position assumption,"
Turkish Journal of Mathematics: Vol. 39:
No.
6, Article 3.
https://doi.org/10.3906/mat-1410-12
Available at:
https://journals.tubitak.gov.tr/math/vol39/iss6/3
