Computing the Stretch Factor of Paths, Trees, and Cycles in Weighted Fixed Orientation Metrics

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review

Let G be a graph embedded in the L_1-plane. The stretch factor of G is the maximum over all pairs of distinct vertices p and q of G of the ratio L_1^G(p,q)/L_1(p,q), where L_1^G(p,q) is the L_1-distance in G between p and q. We show how to compute the stretch factor of an n-vertex path in O(n*(log n)^2) worst-case time and O(n) space and we mention generalizations to trees and cycles, to general weighted fixed orientation metrics, and to higher dimensions.
Original languageEnglish
Title of host publicationProceedings of the 20th Annual Canadian Conference on Computational Geometry -  CCCG 2008 : August 13-15, McGill University, Montréal, Québec, Canada
Number of pages4
PublisherCCCG - Canadian Conference on Computational Geometry, Ottawa, Ontario, Canada
Publication date2008
Pages59-62
Publication statusPublished - 2008
EventCanadian Conference on Computational Geometry - Montreal, Canada
Duration: 13 Aug 200815 Aug 2008
Conference number: 20

Conference

ConferenceCanadian Conference on Computational Geometry
Nummer20
LandCanada
ByMontreal
Periode13/08/200815/08/2008

ID: 9617435