Crossing minimization in linear embeddings of graphs

Shinya Masuda, K. Nakajima, Toshinobu Kashiwabara, T. Fujisawa

IEEE Transactions on Computers · 1990 · 68 citations · 15 references

Concepts

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.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">&gt;</ETX>

References

15