Fixed edge-length graph drawing is NP-hard
From MaRDI portal
Publication:1813977
DOI10.1016/0166-218X(90)90110-XzbMath0744.05053WikidataQ56001823 ScholiaQ56001823MaRDI QIDQ1813977
Nicholas C. Wormald, Peter Eades
Publication date: 25 June 1992
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Planar graphs; geometric and topological aspects of graph theory (05C10) Graph algorithms (graph-theoretic aspects) (05C85) Applications of graph theory to circuits and networks (94C15)
Related Items
HV-planarity: algorithms and complexity, The logic engine and the realization problem for nearest neighbor graphs, Planar straight-line realizations of 2-trees with prescribed edge lengths, On Edge-Length Ratios of Partial 2-Trees, Unnamed Item, Unit-length rectangular drawings of graphs, On the edge-length ratio of planar graphs, Equilateral Spherical Drawings of Planar Cayley Graphs, On the Computational Complexity of Degenerate Unit Distance Representations of Graphs, Data-driven graph drawing techniques with applications for conveyor systems, On the edge-length ratio of outerplanar graphs, An Experimental Study on Distance-Based Graph Drawing, On the Hardness of Orthogonal-Order Preserving Graph Drawing, Degree-constrained orientations of embedded graphs, A note on isosceles planar graph drawing, On the Edge-Length Ratio of 2-Trees, Free edge lengths in plane graphs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A linear algorithm for embedding planar graphs using PQ-trees
- The complexity of drawing trees nicely
- Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
- Algorithms for drawing graphs: An annotated bibliography
- A Class Of Abelian Groups
- Integer flows
- Universality considerations in VLSI circuits
- Efficient Planarity Testing
- Two-Processor Scheduling with Start-Times and Deadlines
- The NP-completeness column: An ongoing guide
- The NP-completeness column: An ongoing guide
