Welcome!
To use the personalized features of this site, please log in or register.
If you have forgotten your username or password, we can help.
My Menu
Saved Items

Triangulations without Minimum-Weight Drawing

Cao An WangContact Information, Francis Y. ChinContact Information 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.

Contact Information Cao An Wang
Email: wang@garfield.cs.mun.ca

Contact Information Francis Y. Chin
Email: chin@csis.hku.hk
Fulltext Preview (Small, Large)
Image of the first page of the fulltext

References secured to subscribers.



Export this chapter
Export this chapter as RIS | Text
 
Remote Address: 38.107.191.109 • Server: mpweb21
HTTP User Agent: CCBot/1.0 (+http://www.commoncrawl.org/bot.html)