Triangulations without minimum-weight drawing

被引：0
|
作者：
Wang, Cao An [1 ]
Chin, Francis Y. [2 ]
Yang, Boting [1 ]
机构：
[1] Department of Computer Science, Memorial University of Newfoundland, St. John’s,NL,A1B 3X5, Canada
[2] Department of Computer Science and Information Systems, The University of Hong Kong, Pokfulam Road, Hong Kong
来源：
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) | 2000年 / 1767卷
基金：
加拿大自然科学与工程研究理事会;
关键词：
Drawing (graphics) - Musculoskeletal system;
D O I：
10.1007/3-540-46521-9_14
中图分类号：
学科分类号：
摘要：
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. © Springer-Verlag Berlin Heidelberg 2000.
引用
收藏
页码：163 / 173
相关论文
共 50 条
  • [1] Triangulations without minimum-weight drawing
    Wang, CA
    Chin, FY
    Yang, BT
    INFORMATION PROCESSING LETTERS, 2000, 74 (5-6) : 183 - 189
  • [2] Triangulations without minimum-weight drawing
    Wang, CA
    Chin, FY
    Yang, BT
    ALGORITHMS AND COMPLEXITY, 2000, 1767 : 163 - 173
  • [3] Approximating minimum-weight triangulations in three dimensions
    Aronov, B
    Fortune, S
    DISCRETE & COMPUTATIONAL GEOMETRY, 1999, 21 (04) : 527 - 549
  • [4] Approximating Minimum-Weight Triangulations in Three Dimensions
    B. Aronov
    S. Fortune
    Discrete & Computational Geometry, 1999, 21 : 527 - 549
  • [5] Drawing outerplanar minimum weight triangulations
    Department of Computer Science, Williams College, Williamstown, MA 01267, United States
    不详
    Inf. Process. Lett., 5 (253-260):
  • [6] Drawing outerplanar minimum weight triangulations
    Lenhart, W
    Liotta, G
    INFORMATION PROCESSING LETTERS, 1996, 57 (05) : 253 - 260
  • [7] Limit theorems for minimum-weight triangulations, other Euclidean Functionals, and probabilistic recurrence relations
    Golin, MJ
    PROCEEDINGS OF THE SEVENTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, 1996, : 252 - 260
  • [8] Construction of minimum-weight spanners
    Sigurd, M
    Zachariasen, M
    ALGORITHMS ESA 2004, PROCEEDINGS, 2004, 3221 : 797 - 808
  • [9] Minimum-Weight Edge Discriminators in Hypergraphs
    Bhattacharya, Bhaswar B.
    Das, Sayantan
    Ganguly, Shirshendu
    ELECTRONIC JOURNAL OF COMBINATORICS, 2014, 21 (03):
  • [10] THE MINIMUM-WEIGHT DESIGN OF STRUCTURAL FRAMES
    FOULKES, J
    PROCEEDINGS OF THE ROYAL SOCIETY OF LONDON SERIES A-MATHEMATICAL AND PHYSICAL SCIENCES, 1954, 223 (1155): : 482 - 494
12345