Show simple item record

Crossing Minimization in the Straight-Line Embedding of Graphs.

dc.contributor.authorMasuda, Sumioen_US
dc.contributor.authorNakajima, Kazuoen_US
dc.contributor.authorKashiwabara, Toshinobuen_US
dc.contributor.authorFujisawa, Toshioen_US
dc.description.abstractThe problem of embedding a graph in the plane with the minimum number of edgecrossings arises in some circuit layout problems. It has been known that this problem is in general NP-hard. An interesting and relevant problem in the area of book embedding was recently shown to be NP-hard. This result implies that the former problem is NP-hard even when the vertices are placed on a straight line l and the edges are drawn completely on either side of l. In this paper, we show that the problem remains NP-hard even if, in addition to these constraints, the positions of the vertices on SCRIPT l are predetermined.en_US
dc.format.extent471686 bytes
dc.relation.ispartofseriesISR; TR 1987-43en_US
dc.titleCrossing Minimization in the Straight-Line Embedding of Graphs.en_US
dc.typeTechnical Reporten_US

Files in this item


This item appears in the following Collection(s)

Show simple item record