Algorithms for finding non-crossing paths with minimum total length in plane graphs

Jun Ya Takahashi; Hitoshi Suzuki; Takao Nishizeki

doi:10.1007/3-540-56279-6_92

Algorithms for finding non-crossing paths with minimum total length in plane graphs

Jun Ya Takahashi, Hitoshi Suzuki, Takao Nishizeki

INF - System Information Sciences

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

9 Citations (Scopus)

Abstract

Let G be an undirected plane graph with non-negative edge length, and let k terminal pairs lie on two specified face boundaries. This paper presents an algorithm for finding k “non-crossing paths” in G, each connecting a terminal pair, whose total length is minimum. Here “non-crossing paths” may share common vertices or edges but do not cross each other in the plane. The algorithm runs in time O(n log n) where n is the number of vertices in G.

Original language	English
Title of host publication	Algorithms and Computation - 3rd International Symposium, ISAAC 1992, Proceedings
Editors	Takao Nishizeki, Toshihide Ibaraki, Kazuo Iwama, Masafurni Yamashita, Yasuyoshi Inagaki
Publisher	Springer Verlag
Pages	400-409
Number of pages	10
ISBN (Print)	9783540562795
DOIs	https://doi.org/10.1007/3-540-56279-6_92
Publication status	Published - 1992
Event	3rd International Symposium on Algorithms and Computation, ISAAC 1992 - Nagoya, Japan Duration: 1992 Dec 16 → 1992 Dec 18

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	650 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Other

Other	3rd International Symposium on Algorithms and Computation, ISAAC 1992
Country/Territory	Japan
City	Nagoya
Period	92/12/16 → 92/12/18

ASJC Scopus subject areas

Theoretical Computer Science
Computer Science(all)

Access to Document

10.1007/3-540-56279-6_92

Cite this

Takahashi, J. Y., Suzuki, H., & Nishizeki, T. (1992). Algorithms for finding non-crossing paths with minimum total length in plane graphs. In T. Nishizeki, T. Ibaraki, K. Iwama, M. Yamashita, & Y. Inagaki (Eds.), Algorithms and Computation - 3rd International Symposium, ISAAC 1992, Proceedings (pp. 400-409). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 650 LNCS). Springer Verlag. https://doi.org/10.1007/3-540-56279-6_92

Algorithms for finding non-crossing paths with minimum total length in plane graphs. / Takahashi, Jun Ya; Suzuki, Hitoshi; Nishizeki, Takao.
Algorithms and Computation - 3rd International Symposium, ISAAC 1992, Proceedings. ed. / Takao Nishizeki; Toshihide Ibaraki; Kazuo Iwama; Masafurni Yamashita; Yasuyoshi Inagaki. Springer Verlag, 1992. p. 400-409 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 650 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Takahashi, JY, Suzuki, H & Nishizeki, T 1992, Algorithms for finding non-crossing paths with minimum total length in plane graphs. in T Nishizeki, T Ibaraki, K Iwama, M Yamashita & Y Inagaki (eds), Algorithms and Computation - 3rd International Symposium, ISAAC 1992, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 650 LNCS, Springer Verlag, pp. 400-409, 3rd International Symposium on Algorithms and Computation, ISAAC 1992, Nagoya, Japan, 92/12/16. https://doi.org/10.1007/3-540-56279-6_92

Takahashi JY, Suzuki H, Nishizeki T. Algorithms for finding non-crossing paths with minimum total length in plane graphs. In Nishizeki T, Ibaraki T, Iwama K, Yamashita M, Inagaki Y, editors, Algorithms and Computation - 3rd International Symposium, ISAAC 1992, Proceedings. Springer Verlag. 1992. p. 400-409. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/3-540-56279-6_92

Takahashi, Jun Ya ; Suzuki, Hitoshi ; Nishizeki, Takao. / Algorithms for finding non-crossing paths with minimum total length in plane graphs. Algorithms and Computation - 3rd International Symposium, ISAAC 1992, Proceedings. editor / Takao Nishizeki ; Toshihide Ibaraki ; Kazuo Iwama ; Masafurni Yamashita ; Yasuyoshi Inagaki. Springer Verlag, 1992. pp. 400-409 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{b558ba329f764202a30f8de1141f713e,

title = "Algorithms for finding non-crossing paths with minimum total length in plane graphs",

abstract = "Let G be an undirected plane graph with non-negative edge length, and let k terminal pairs lie on two specified face boundaries. This paper presents an algorithm for finding k “non-crossing paths” in G, each connecting a terminal pair, whose total length is minimum. Here “non-crossing paths” may share common vertices or edges but do not cross each other in the plane. The algorithm runs in time O(n log n) where n is the number of vertices in G.",

author = "Takahashi, {Jun Ya} and Hitoshi Suzuki and Takao Nishizeki",

note = "Publisher Copyright: {\textcopyright} Springer-Verlag Berlin Heidelberg 1992.; 3rd International Symposium on Algorithms and Computation, ISAAC 1992 ; Conference date: 16-12-1992 Through 18-12-1992",

year = "1992",

doi = "10.1007/3-540-56279-6_92",

language = "English",

isbn = "9783540562795",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "400--409",

editor = "Takao Nishizeki and Toshihide Ibaraki and Kazuo Iwama and Masafurni Yamashita and Yasuyoshi Inagaki",

booktitle = "Algorithms and Computation - 3rd International Symposium, ISAAC 1992, Proceedings",

}

TY - GEN

T1 - Algorithms for finding non-crossing paths with minimum total length in plane graphs

AU - Takahashi, Jun Ya

AU - Suzuki, Hitoshi

AU - Nishizeki, Takao

N1 - Publisher Copyright: © Springer-Verlag Berlin Heidelberg 1992.

PY - 1992

Y1 - 1992

N2 - Let G be an undirected plane graph with non-negative edge length, and let k terminal pairs lie on two specified face boundaries. This paper presents an algorithm for finding k “non-crossing paths” in G, each connecting a terminal pair, whose total length is minimum. Here “non-crossing paths” may share common vertices or edges but do not cross each other in the plane. The algorithm runs in time O(n log n) where n is the number of vertices in G.

AB - Let G be an undirected plane graph with non-negative edge length, and let k terminal pairs lie on two specified face boundaries. This paper presents an algorithm for finding k “non-crossing paths” in G, each connecting a terminal pair, whose total length is minimum. Here “non-crossing paths” may share common vertices or edges but do not cross each other in the plane. The algorithm runs in time O(n log n) where n is the number of vertices in G.

UR - http://www.scopus.com/inward/record.url?scp=84990196492&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84990196492&partnerID=8YFLogxK

U2 - 10.1007/3-540-56279-6_92

DO - 10.1007/3-540-56279-6_92

M3 - Conference contribution

AN - SCOPUS:84990196492

SN - 9783540562795

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 400

EP - 409

BT - Algorithms and Computation - 3rd International Symposium, ISAAC 1992, Proceedings

A2 - Nishizeki, Takao

A2 - Ibaraki, Toshihide

A2 - Iwama, Kazuo

A2 - Yamashita, Masafurni

A2 - Inagaki, Yasuyoshi

PB - Springer Verlag

T2 - 3rd International Symposium on Algorithms and Computation, ISAAC 1992

Y2 - 16 December 1992 through 18 December 1992

ER -

Algorithms for finding non-crossing paths with minimum total length in plane graphs

Abstract

Publication series

Other

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this