File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Article: Maximum weight triangulation and graph drawing

TitleMaximum weight triangulation and graph drawing
Authors
Wang, CAChin, FYYang, BT
Issue Date1999
PublisherElsevier BV. The Journal's web site is located at http://www.elsevier.com/locate/ipl
Citation
Information Processing Letters, 1999, v. 70 n. 1, p. 17-22 How to Cite?
DOI: http://dx.doi.org/10.1016/S0020-0190(99)00037-X
AbstractIn this paper, we investigate the maximum weight triangulation of a convex polygon and its application to graph drawing. We can find the maximum weight triangulation of a special n-gon which inscribed on a circle in O(n2) time. 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 further show that a tree always admits a maximum weight drawing if the internal nodes of the tree connect to at most 2 non-leaf nodes, and the drawing can be done in O(n) time. Finally, we prove a property of maximum planar graphs which do not admit a maximum weight drawing on any convex point set.
Persistent Identifierhttp://hdl.handle.net/10722/152273
ISSN
0020-0190
2023 Impact Factor: 0.7
2023 SCImago Journal Rankings: 0.404
ISI Accession Number ID
WOS:000080537800004
References
References in Scopus

 

DC FieldValueLanguage
dc.contributor.authorWang, CAen_US
dc.contributor.authorChin, FYen_US
dc.contributor.authorYang, BTen_US
dc.date.accessioned2012-06-26T06:36:52Z-
dc.date.available2012-06-26T06:36:52Z-
dc.date.issued1999en_US
dc.identifier.citationInformation Processing Letters, 1999, v. 70 n. 1, p. 17-22en_US
dc.identifier.issn0020-0190en_US
dc.identifier.urihttp://hdl.handle.net/10722/152273-
dc.description.abstractIn this paper, we investigate the maximum weight triangulation of a convex polygon and its application to graph drawing. We can find the maximum weight triangulation of a special n-gon which inscribed on a circle in O(n2) time. 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 further show that a tree always admits a maximum weight drawing if the internal nodes of the tree connect to at most 2 non-leaf nodes, and the drawing can be done in O(n) time. Finally, we prove a property of maximum planar graphs which do not admit a maximum weight drawing on any convex point set.en_US
dc.languageengen_US
dc.publisherElsevier BV. The Journal's web site is located at http://www.elsevier.com/locate/iplen_US
dc.relation.ispartofInformation Processing Lettersen_US
dc.rightsInformation Processing Letters. Copyright © Elsevier BV.-
dc.titleMaximum weight triangulation and graph drawingen_US
dc.typeArticleen_US
dc.identifier.emailChin, FY:chin@cs.hku.hken_US
dc.identifier.authorityChin, FY=rp00105en_US
dc.description.naturelink_to_subscribed_fulltexten_US
dc.identifier.doi10.1016/S0020-0190(99)00037-Xen_US
dc.identifier.scopuseid_2-s2.0-0033574360en_US
dc.identifier.hkuros42545-
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-0033574360&selection=ref&src=s&origin=recordpageen_US
dc.identifier.volume70en_US
dc.identifier.issue1en_US
dc.identifier.spage17en_US
dc.identifier.epage22en_US
dc.identifier.isiWOS:000080537800004-
dc.publisher.placeNetherlandsen_US
dc.identifier.scopusauthoridWang, CA=7501646353en_US
dc.identifier.scopusauthoridChin, FY=7005101915en_US
dc.identifier.scopusauthoridYang, BT=22137306700en_US
dc.identifier.issnl0020-0190-

Export via OAI-PMH Interface in XML Formats

OR

Export to Other Non-XML Formats