IEEE Transactions on Computers · 1990 · 68 citations · 15 references
Natural SciencesComputer ScienceMathematicsAlgorithmsCombinatoricsOptimizationCombinatorial OptimizationGeometric OptimizationGraph AlgorithmsGraph Layout AlgorithmsGraph TheoryCircuit Graph TheoryCrossing MinimizationEdge Crossings ReductionEdge-crossing ReductionGraph Crossing MinimizationGraph Embeddings
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">></ETX>
15
John E. Hopcroft, Robert E. Tarjan · Journal of the ACM · 1974 · 1.1K citations · Full text
Computer-Aided Design · 1985 · 931 citations
The NP-completeness column: An ongoing guide
David S. Johnson · Journal of Algorithms · 1986 · 803 citations
Crossing Number is NP-Complete
M. R. Garey, David S. Johnson · SIAM Journal on Algebraic and Discrete Methods · 1983 · 669 citations