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

Christian Wulff-Nilsen

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

Department of Computer Science

Abstract

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 language	English
Title of host publication	Proceedings of the 20th Annual Canadian Conference on Computational Geometry - CCCG 2008 : August 13-15, McGill University, Montréal, Québec, Canada
Number of pages	4
Publisher	CCCG - Canadian Conference on Computational Geometry, Ottawa, Ontario, Canada
Publication date	2008
Pages	59-62
Publication status	Published - 2008
Event	Canadian Conference on Computational Geometry - Montreal, Canada Duration: 13 Aug 2008 → 15 Aug 2008 Conference number: 20

Conference

Conference	Canadian Conference on Computational Geometry
Number	20
Country/Territory	Canada
City	Montreal
Period	13/08/2008 → 15/08/2008

Access to Document

Cite this

Wulff-Nilsen, C. (2008). Computing the Stretch Factor of Paths, Trees, and Cycles in Weighted Fixed Orientation Metrics. In Proceedings of the 20th Annual Canadian Conference on Computational Geometry - CCCG 2008: August 13-15, McGill University, Montréal, Québec, Canada (pp. 59-62). CCCG - Canadian Conference on Computational Geometry, Ottawa, Ontario, Canada. http://www.cccg.ca/proceedings/2008/out_N_N.pdf

Computing the Stretch Factor of Paths, Trees, and Cycles in Weighted Fixed Orientation Metrics. / Wulff-Nilsen, Christian.

Proceedings of the 20th Annual Canadian Conference on Computational Geometry - CCCG 2008: August 13-15, McGill University, Montréal, Québec, Canada. CCCG - Canadian Conference on Computational Geometry, Ottawa, Ontario, Canada, 2008. p. 59-62.

Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

Wulff-Nilsen, C 2008, Computing the Stretch Factor of Paths, Trees, and Cycles in Weighted Fixed Orientation Metrics. in Proceedings of the 20th Annual Canadian Conference on Computational Geometry - CCCG 2008: August 13-15, McGill University, Montréal, Québec, Canada. CCCG - Canadian Conference on Computational Geometry, Ottawa, Ontario, Canada, pp. 59-62, Canadian Conference on Computational Geometry, Montreal, Canada, 13/08/2008. <http://www.cccg.ca/proceedings/2008/out_N_N.pdf>

Wulff-Nilsen, Christian. / Computing the Stretch Factor of Paths, Trees, and Cycles in Weighted Fixed Orientation Metrics. Proceedings of the 20th Annual Canadian Conference on Computational Geometry - CCCG 2008: August 13-15, McGill University, Montréal, Québec, Canada. CCCG - Canadian Conference on Computational Geometry, Ottawa, Ontario, Canada, 2008. pp. 59-62

@inproceedings{1cef7590de5311ddb5fc000ea68e967b,

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

abstract = "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.",

author = "Christian Wulff-Nilsen",

year = "2008",

language = "English",

pages = "59--62",

booktitle = "Proceedings of the 20th Annual Canadian Conference on Computational Geometry - CCCG 2008",

publisher = "CCCG - Canadian Conference on Computational Geometry, Ottawa, Ontario, Canada",

note = "Canadian Conference on Computational Geometry ; Conference date: 13-08-2008 Through 15-08-2008",

}

TY - GEN

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

AU - Wulff-Nilsen, Christian

N1 - Conference code: 20

PY - 2008

Y1 - 2008

N2 - 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.

AB - 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.

M3 - Article in proceedings

SP - 59

EP - 62

BT - Proceedings of the 20th Annual Canadian Conference on Computational Geometry - CCCG 2008

PB - CCCG - Canadian Conference on Computational Geometry, Ottawa, Ontario, Canada

T2 - Canadian Conference on Computational Geometry

Y2 - 13 August 2008 through 15 August 2008

ER -

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

Abstract

Conference

Access to Document

Fingerprint

Cite this