An NP-Hard Crossing Minimization Problem for Computer Network Layout.

Thumbnail Image
Files
TR_86-80.pdf(953.94 KB)
No. of downloads: 813
Publication or External Link
Date
1986
Authors
Masuda, Sumio
Kashiwabara, Toshinobu
Nakajima, Kazuo
Fujisawa, Toshio
Advisor
Citation
DRUM DOI
Abstract
A layout problem of computer communication network is formulated graph-theoretically as follows: "Given a simple graph G = (V,E), find an embedding of G with the minimum number of edge-crossings such that (i) the vertices in V are placed on the circumference of a circle C, and (ii) the edges in E are drawn only inside C." In this paper, this problem will be shown to be NP-hard. Therefore, it is very likely to be intractable.
Notes
Rights