Maximum weight triangulation and graph drawing

In this paper, we investigate the maximum weight triangulation of a convex polygon and its application to graph drawing. We can find the maximum weigh t triangulation of a special n-gon which inscribed on a circle in O(n(2)) t ime. The complexity of this algorithm can be reduced to O(n) if the polygon is regular. The algorithm also produces a triangulation approximating the maximum weight triangulation of a convex n-gon with weight ratio 0.5. We fu rther show that a tree always admits a maximum weight drawing if the intern al nodes of the tree connect to at most 2 non-leaf nodes, and the drawing c an be done in O(n) time. Finally, we prove a property of maximum planar gra phs which do not admit a maximum weight drawing on any convex point set. (C ) 1999 Published by Elsevier Science B.V. All rights reserved.