Fixed edge-length graph drawing is NP-hard

AbstractThe problem of drawing a graph with prescribed edge lengths such that edges do not cross is proved NP-hard, even in the case where all edge lengths are one and the graph is 2-connected. The proof is an interesting interplay of geometry and combinatorics. First we use geometrical methods to transform a rather synthetic “Orientation Problem” to our graph drawing problem; then we use combinatorial methods to transform a well-known “Flow Problem” to the orientation problem