Fewer bends point-set embedding with mapping
Md. Emran Chowdhury, Muhammad Jawaherul Alam, Md. Saidur Rahman · 2010
An upward point-set embedding of an upward planar digraph G on a set of points S with a mapping Φ : V(G) → S is an upward planar drawing Γ of G where each vertex of G is placed on a point of S according to Φ. Γ is called an upward topological book embedding of G with the mapping Φ if the points in S are aligned along a straight-line. In this paper, we address the problem of minimizing the total number of bends on the edges in an upward point-set embedding of G with the mapping Φ. We first give an algorithm that finds an upward topological book embedding of G with a mapping if such an embedding exists. Using this result, we then give an algorithm to obtain an upward point-set embedding of G with a mapping if it exists. The drawings obtained by our algorithm for both the problems contain at most (n-3) bends per edge, which improves the previously known upper bound of (2n-3) bends per edge. Furthermore we also find an upper bound on total number of bends in our drawing, which is, to the best of our knowledge, the first result on the total number of bends for the point-set embedding problem.