{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T13:08:58Z","timestamp":1725455338991},"publisher-location":"Berlin, Heidelberg","reference-count":21,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540607236"},{"type":"electronic","value":"9783540493518"}],"license":[{"start":{"date-parts":[[1996,1,1]],"date-time":"1996-01-01T00:00:00Z","timestamp":820454400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1996]]},"DOI":"10.1007\/bfb0021821","type":"book-chapter","created":{"date-parts":[[2005,11,13]],"date-time":"2005-11-13T06:56:38Z","timestamp":1131864998000},"page":"373-384","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["How to draw outerplanar minimum weight triangulations"],"prefix":"10.1007","author":[{"given":"William","family":"Lenhart","sequence":"first","affiliation":[]},{"given":"Giuseppe","family":"Liotta","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,6,17]]},"reference":[{"key":"38_CR1","doi-asserted-by":"crossref","unstructured":"O. Aichholzer, F. Aurenhammer, G. Rote, M. Taschwer. Triangulations Intersect Nicely. Proceedings 11th ACM Symposium on Computational Geometry, Vancouver, Canada, 1995, pp. 220\u2013229.","DOI":"10.1145\/220279.220303"},{"key":"38_CR2","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-349-03521-2","volume-title":"Graph Theory with Applications","author":"J.A. Bondy","year":"1976","unstructured":"J.A. Bondy and U.S.R. Murty. Graph Theory with Applications. Elsevier Science, New York, 1976."},{"key":"38_CR3","doi-asserted-by":"crossref","first-page":"235","DOI":"10.1016\/0925-7721(94)00014-X","volume":"4","author":"G. Battista Di","year":"1994","unstructured":"G. Di Battista, P. Eades, R. Tamassia and I.G. Tollis. Algorithms for Automatic Graph Drawing: An Annotated Bibliography. Computational Geometry: Theory and Applications, 4, 1994, pp. 235\u2013282.","journal-title":"Computational Geometry: Theory and Applications"},{"key":"38_CR4","doi-asserted-by":"crossref","unstructured":"M.T. Dickerson, S.A. McElfresh, M. Montague. New Algorithms and Empirical Findings on Minimum Weight Triangulations Heuristics. Proceedings 11th ACM Symposium on Computational Geometry, Vancouver, Canada, 1995, pp. 238\u2013247.","DOI":"10.1145\/220279.220305"},{"key":"38_CR5","doi-asserted-by":"crossref","unstructured":"P. Eades and S. Whitesides. The Realization Problem for Euclidean Minimum Spanning Tree is NP-hard. Proceedings 10th ACM Symposium on Computational Geometry, Stony Brook NY, USA, 1994, pp. 49\u201356.","DOI":"10.1145\/177424.177507"},{"key":"38_CR6","volume-title":"Computers and Intractability-A Guide to the Theory of NP-Completeness","author":"M.R. Garey","year":"1979","unstructured":"M.R. Garey and D.S. Johnson. Computers and Intractability-A Guide to the Theory of NP-Completeness. Freeman, New York, 1979."},{"key":"38_CR7","volume-title":"M.Sc. Thesis","author":"P.N. Gilbert","year":"1979","unstructured":"P.N. Gilbert. New Results in Planar Triangulations. M.Sc. Thesis, Coordinated Science Laboratory, University of Illinois, Urbana, IL, 1979."},{"key":"38_CR8","doi-asserted-by":"publisher","first-page":"533","DOI":"10.1007\/BF01188718","volume":"12","author":"L.S. Heath","year":"1994","unstructured":"L.S. Heath and S.V. Pemmaraju. New Results for the Minimum Weight Triangulation Problem. Algorithmica, 12, 1994 pp. 533\u2013552.","journal-title":"Algorithmica"},{"key":"38_CR9","first-page":"13","volume":"4","author":"J.M. Keil","year":"1994","unstructured":"J.M. Keil. Computing a Subgraph of the Minimum Weight Triangulation. Computational Geometry: Theory and Applications, 4, 1994, pp. 13\u201326.","journal-title":"Computational Geometry: Theory and Applications"},{"key":"38_CR10","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1016\/0020-0190(80)90062-9","volume":"10","author":"D. G. Kirkpatrick","year":"1980","unstructured":"D. G. Kirkpatrick. A Note on Delaunay and Optimal Triangulations, information Processing Letters, 10, 1980, pp. 127\u2013128.","journal-title":"information Processing Letters"},{"key":"38_CR11","doi-asserted-by":"crossref","first-page":"121","DOI":"10.1016\/S0167-5060(08)70044-X","volume":"9","author":"G.T. Klincsek","year":"1980","unstructured":"G.T. Klincsek. Minimal triangulations of Polygonal Domains. Ann. Discrete Math., 9, 1980, pp. 121\u2013123.","journal-title":"Ann. Discrete Math."},{"key":"38_CR12","doi-asserted-by":"publisher","first-page":"247","DOI":"10.1016\/0020-0190(87)90170-0","volume":"25","author":"C. Levcopoulos","year":"1987","unstructured":"C. Levcopoulos. An \u03a9(\u221an) Lower Bound for the Nonoptimality of the Greedy Triangulation. Information Processing Letters, 25, 1987, pp. 247\u2013251.","journal-title":"Information Processing Letters"},{"key":"38_CR13","doi-asserted-by":"publisher","first-page":"175","DOI":"10.1007\/BF01840358","volume":"2","author":"C. Levcopoulos","year":"1987","unstructured":"C. Levcopoulos and A. Lingas. On Approximation Behavior of the Greedy Triangulation for Convex Polygons. Algorithmica, 2, 1987, pp. 175\u2013193.","journal-title":"Algorithmica"},{"key":"38_CR14","unstructured":"A. Lingas. A Linear-Time Heuristic for Minimum Weight Triangulation of Convex Polygons. Proc. 23rd Allerton Conference on Computing, Communication, and Control, Urbana, 1985, pp. 480\u2013485."},{"key":"38_CR15","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1016\/0020-0190(86)90038-4","volume":"22","author":"A. Lingas","year":"1986","unstructured":"A. Lingas. The Greedy and Delaunay Triangulations are not Bad in the Average Case. Information Processing Letters, 22, 1986, pp. 25\u201331.","journal-title":"Information Processing Letters"},{"key":"38_CR16","doi-asserted-by":"crossref","first-page":"646","DOI":"10.1137\/0608053","volume":"8","author":"A. Lingas","year":"1987","unstructured":"A. Lingas. A New Heuristic for Minimum Weight Triangulation. SIAM J. Algebraic Discrete Methods, 8, 1987, pp. 646\u2013658.","journal-title":"SIAM J. Algebraic Discrete Methods"},{"key":"38_CR17","doi-asserted-by":"crossref","unstructured":"E.L. Lloyd. On Triangulations of a Set of Points in the Plane. Proceedings of the 18th Conference on the Foundations of Computer Science, Providence, RI, 1977, pp. 228\u2013240.","DOI":"10.1109\/SFCS.1977.21"},{"key":"38_CR18","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1016\/0020-0190(79)90104-2","volume":"9","author":"K. Manacher","year":"1979","unstructured":"K. Manacher, L. Zobrist. Neither the Greedy nor the Delaunay Triangulation of a Planar Point Set Approximates the Optimal Triangulation. Information Processing Letters, 9, 1979, pp. 31\u201334.","journal-title":"Information Processing Letters"},{"key":"38_CR19","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1016\/0020-0190(92)90129-J","volume":"42","author":"H. Meijer","year":"1992","unstructured":"H. Meijer and D. Rappaport. Computing the Minimum Weight Triangulation of a Set of Linearly Ordered Points. Information Processing Letters, 42, 1992, pp. 35\u201338.","journal-title":"Information Processing Letters"},{"key":"38_CR20","doi-asserted-by":"crossref","unstructured":"C. Monma and S. Suri. Transitions in Geometric Minimum Spanning Trees. Proc. 7th ACM Symposium on Computational Geometry, 1991, pp. 239\u2013249.","DOI":"10.1145\/109648.109675"},{"key":"38_CR21","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-1098-6","volume-title":"Computational Geometry \u2014 an Introduction","author":"F. P. Preparata","year":"1985","unstructured":"F. P. Preparata and M. I. Shamos, Computational Geometry \u2014 an Introduction. Springer-Verlag, New York, 1985."}],"container-title":["Lecture Notes in Computer Science","Graph Drawing"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BFb0021821","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,1,9]],"date-time":"2020-01-09T04:30:24Z","timestamp":1578544224000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BFb0021821"}},"subtitle":["Extended abstract"],"short-title":[],"issued":{"date-parts":[[1996]]},"ISBN":["9783540607236","9783540493518"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/bfb0021821","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1996]]},"assertion":[{"value":"17 June 2005","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}