Algorithms for finding noncrossing paths with minimum total length in plane graphs

Jun‐Ya ‐Y Takahashi; Hitoshi Suzuki; Takao Nishizeki

doi:10.1002/ecjc.4430780401

Algorithms for finding noncrossing paths with minimum total length in plane graphs

Jun‐Ya ‐Y Takahashi, Hitoshi Suzuki, Takao Nishizeki

INF - System Information Sciences

Tohoku University

Research output: Contribution to journal › Article › peer-review

Abstract

Assume that G is an undirected planar graph and the edge length of G is a nonnegative real number. When k terminal pairs are specified on two specified face boundaries, this paper gives an algorithm that derives the “noncrossing paths” with the minimum sum of lengths that connects the respective terminal pairs. By the noncrossing paths is meant the paths which do not cross on the plane, although the point or the edge may be shared. the computation time of the proposed algorithm is O(n log n), where n is the number of points on the planar graph G; k need not be a constant.

Original language	English
Pages (from-to)	1-15
Number of pages	15
Journal	Electronics and Communications in Japan, Part III: Fundamental Electronic Science (English translation of Denshi Tsushin Gakkai Ronbunshi)
Volume	78
Issue number	4
DOIs	https://doi.org/10.1002/ecjc.4430780401
Publication status	Published - 1995 Apr

Keywords

algorithm
noncrossing paths
Planar graph
shortest‐path problem
VLSI single‐layer routing

Access to Document

10.1002/ecjc.4430780401

Cite this

@article{47b7132479e74a50a22f250996aa2a84,

title = "Algorithms for finding noncrossing paths with minimum total length in plane graphs",

abstract = "Assume that G is an undirected planar graph and the edge length of G is a nonnegative real number. When k terminal pairs are specified on two specified face boundaries, this paper gives an algorithm that derives the “noncrossing paths” with the minimum sum of lengths that connects the respective terminal pairs. By the noncrossing paths is meant the paths which do not cross on the plane, although the point or the edge may be shared. the computation time of the proposed algorithm is O(n log n), where n is the number of points on the planar graph G; k need not be a constant.",

keywords = "algorithm, noncrossing paths, Planar graph, shortest‐path problem, VLSI single‐layer routing",

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

year = "1995",

month = apr,

doi = "10.1002/ecjc.4430780401",

language = "English",

volume = "78",

pages = "1--15",

journal = "Electronics and Communications in Japan, Part III: Fundamental Electronic Science (English translation of Denshi Tsushin Gakkai Ronbunshi)",

issn = "1042-0967",

publisher = "John Wiley & Sons Inc.",

number = "4",

}

Algorithms for finding noncrossing paths with minimum total length in plane graphs. / Takahashi, Jun‐Ya ‐Y; Suzuki, Hitoshi; Nishizeki, Takao.
In: Electronics and Communications in Japan, Part III: Fundamental Electronic Science (English translation of Denshi Tsushin Gakkai Ronbunshi), Vol. 78, No. 4, 04.1995, p. 1-15.

Research output: Contribution to journal › Article › peer-review

TY - JOUR

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

AU - Takahashi, Jun‐Ya ‐Y

AU - Suzuki, Hitoshi

AU - Nishizeki, Takao

PY - 1995/4

Y1 - 1995/4

N2 - Assume that G is an undirected planar graph and the edge length of G is a nonnegative real number. When k terminal pairs are specified on two specified face boundaries, this paper gives an algorithm that derives the “noncrossing paths” with the minimum sum of lengths that connects the respective terminal pairs. By the noncrossing paths is meant the paths which do not cross on the plane, although the point or the edge may be shared. the computation time of the proposed algorithm is O(n log n), where n is the number of points on the planar graph G; k need not be a constant.

AB - Assume that G is an undirected planar graph and the edge length of G is a nonnegative real number. When k terminal pairs are specified on two specified face boundaries, this paper gives an algorithm that derives the “noncrossing paths” with the minimum sum of lengths that connects the respective terminal pairs. By the noncrossing paths is meant the paths which do not cross on the plane, although the point or the edge may be shared. the computation time of the proposed algorithm is O(n log n), where n is the number of points on the planar graph G; k need not be a constant.

KW - algorithm

KW - noncrossing paths

KW - Planar graph

KW - shortest‐path problem

KW - VLSI single‐layer routing

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

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

U2 - 10.1002/ecjc.4430780401

DO - 10.1002/ecjc.4430780401

M3 - Article

AN - SCOPUS:0029282483

SN - 1042-0967

VL - 78

SP - 1

EP - 15

JO - Electronics and Communications in Japan, Part III: Fundamental Electronic Science (English translation of Denshi Tsushin Gakkai Ronbunshi)

JF - Electronics and Communications in Japan, Part III: Fundamental Electronic Science (English translation of Denshi Tsushin Gakkai Ronbunshi)

IS - 4

ER -

Algorithms for finding noncrossing paths with minimum total length in plane graphs

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this