##### Fixed edge-length graph drawing is NP-hard

Review articleOpen access###### Peter Eades - No affiliation found

**1990/08/01**DOI: 10.1016/0166-218X(90)90110-X

*Full-length article***Journal:**Discrete Applied Mathematics

##### Abstract:

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.

Request full text