Fixed edge-length graph drawing is NP-hard
Review articleOpen access
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

References (0)

Cited By (0)

No reference data.
No citation data.
Advertisement
Join Copernicus Academic and get access to over 12 million papers authored by 7+ million academics.
Join for free!