A monotone drawing of a graph G is a straight-line drawing of G such that, for every pair of vertices u, w in G, there exists a path P_(uw) in G that is monotone in some direction l. (Namely, the order of the orthogonal projections of the vertices of P_(uw) on l is the same as the order they appear in P_(uw)) The problem of finding monotone drawing for trees has been studied in several recent papers. The main focus is to reduce the size of the drawing. Currently, the smallest drawing size is O(n~(1.5)) × O(n~(1.5))- In this paper, we present a linear time algorithm for constructing monotone drawing of trees on a grid of size at most O(n~(1.205) × O(n~(1.205). This is the first result achieving o(n~3) drawing area for solving this problem.
展开▼
