Name
Abstract | ||
|---|---|---|
The problem of embedding a graph in the plane with the minimum number of edge crossings arises in some circuit layout problems. It has been known to be NP-hard in general. Recently, in the area of book embedding, this problem was shown to be NP-hard even when the vertices are placed on a straight line l. The authors show that the problem remains NP-hard even if, in addition to these constraints, the positions of the vertices on l are predetermined. |
Year | DOI | Venue |
|---|---|---|
1990 | 10.1109/12.46286 | Computers, IEEE Transactions |
Keywords | Field | DocType |
circuit layout CAD,computational complexity,graph theory,minimisation,NP-hard,circuit layout problems,crossing minimisation,linear embeddings of graphs | Graph theory,Discrete mathematics,Graph,Embedding,Computer science,Parallel computing,Minimisation (psychology),Minification,Computational complexity theory | Journal |
Volume | Issue | ISSN |
39 | 1 | 0018-9340 |
Citations | PageRank | References |
35 | 2.02 | 5 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Sumio Masuda | 1 | 150 | 20.26 |
| Kazuo Nakajima | 2 | 80 | 8.16 |
| Toshinobu Kashiwabara | 3 | 106 | 16.79 |
| Toshio Fujisawa | 4 | 92 | 15.13 |