Shortest Noncrossing Paths in Plane Graphs

Jun Ya Takahashi; Hitoshi Suzuki; Takao Nishizeki

doi:10.1007/bf01955681

Shortest Noncrossing Paths in Plane Graphs

Jun Ya Takahashi, Hitoshi Suzuki, Takao Nishizeki

INF - System Information Sciences

Tohoku University

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

16 Citations (Scopus)

Abstract

Let G be an undirected plane graph with nonnegative edge length, and let k terminal pairs lie on two specified face boundaries. This paper presents an algorithm for finding k "noncrossing paths" in G, each connecting a terminal pair, and whose total length is minimum. Noncrossing 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 and k is an arbitrary integer.

Original language	English
Pages (from-to)	339-357
Number of pages	19
Journal	Algorithmica
Volume	16
Issue number	3
DOIs	https://doi.org/10.1007/bf01955681
Publication status	Published - 1996 Sept

Keywords

Noncrossing paths
Plane graphs
Shortest path
Single-layer routing
VLSI

Access to Document

10.1007/bf01955681

Cite this

@article{5896cfa671c14d58aa61e4afcfb80a02,

title = "Shortest Noncrossing Paths in Plane Graphs",

abstract = "Let G be an undirected plane graph with nonnegative edge length, and let k terminal pairs lie on two specified face boundaries. This paper presents an algorithm for finding k {"}noncrossing paths{"} in G, each connecting a terminal pair, and whose total length is minimum. Noncrossing 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 and k is an arbitrary integer.",

keywords = "Noncrossing paths, Plane graphs, Shortest path, Single-layer routing, VLSI",

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

year = "1996",

month = sep,

doi = "10.1007/bf01955681",

language = "English",

volume = "16",

pages = "339--357",

journal = "Algorithmica",

issn = "0178-4617",

publisher = "Springer New York",

number = "3",

}

TY - JOUR

T1 - Shortest Noncrossing Paths in Plane Graphs

AU - Takahashi, Jun Ya

AU - Suzuki, Hitoshi

AU - Nishizeki, Takao

PY - 1996/9

Y1 - 1996/9

N2 - Let G be an undirected plane graph with nonnegative edge length, and let k terminal pairs lie on two specified face boundaries. This paper presents an algorithm for finding k "noncrossing paths" in G, each connecting a terminal pair, and whose total length is minimum. Noncrossing 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 and k is an arbitrary integer.

AB - Let G be an undirected plane graph with nonnegative edge length, and let k terminal pairs lie on two specified face boundaries. This paper presents an algorithm for finding k "noncrossing paths" in G, each connecting a terminal pair, and whose total length is minimum. Noncrossing 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 and k is an arbitrary integer.

KW - Noncrossing paths

KW - Plane graphs

KW - Shortest path

KW - Single-layer routing

KW - VLSI

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

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

U2 - 10.1007/bf01955681

DO - 10.1007/bf01955681

M3 - Article

AN - SCOPUS:0041452088

SN - 0178-4617

VL - 16

SP - 339

EP - 357

JO - Algorithmica

JF - Algorithmica

IS - 3

ER -

Shortest Noncrossing Paths in Plane Graphs

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this