Triangulations without Minimum-Weight Drawing
Cao An Wang6
, Francis Y. Chin7
and Boting Yang6
| (6) |
Department of Computer Science, Memorial University of Newfoundland, St. John’s, Newfoundland, Canada, A1B 3X5 |
| (7) |
Department of Computer Science and Information Systems, The University of Hong Kong, Pokfulam Road, Hong Kong |
Abstract
It is known that some triangulation graphs admit straight-line drawings realizing certain characteristics, e.g., greedy triangulation,
minimum- weight triangulation, Delaunay triangulation, etc.. Lenhart and Liotta [12] in their pioneering paper on “drawable” minimum-weight triangulations raised an open problem: ‘Does every triangulation
graph whose skeleton is a forest admit a minimum-weight drawing?’ In this paper, we answer this problem by disproving it in
the general case and even when the skeleton is restricted to a tree or, in particular, a star.
Keywords Graph drawing - Minimum-weight triangulation
This work is supported by NSERC grant OPG0041629 and RGC grant HKU 541/96E.
References secured to subscribers.