Crossing Minimization in the Straight-Line Embedding of Graphs.

Simple item page
dc.contributor.authorMasuda, Sumioen_US
dc.contributor.authorNakajima, Kazuoen_US
dc.contributor.authorKashiwabara, Toshinobuen_US
dc.contributor.authorFujisawa, Toshioen_US
dc.contributor.departmentISRen_US
dc.date.accessioned2007-05-23T09:36:58Z
dc.date.available2007-05-23T09:36:58Z
dc.date.issued1987en_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.format.mimetypeapplication/pdf
dc.identifier.urihttp://hdl.handle.net/1903/4552
dc.language.isoen_USen_US
dc.relation.ispartofseriesISR; TR 1987-43en_US
dc.titleCrossing Minimization in the Straight-Line Embedding of Graphs.en_US
dc.typeTechnical Reporten_US

Files

Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
TR_87-43.pdf
Size:
460.63 KB
Format:
Adobe Portable Document Format
Download

Collections

Institute for Systems Research Technical Reports