Fixed edge-length graph drawing is NP-hard

DOI10.1016/0166-218X(90)90110-XMaRDI QIDQ1813977zbMATH OpenWikidataFDO

Authors Peter Eades, Nicholas Wormald

Publication date 25 June 1992

Published in Discrete Applied Mathematics (Search for Journal in Brave)

zbMATH Keywords

computational geometryplanar graph2-connected graphgraph layout

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Planar graphs; geometric and topological aspects of graph theory (05C10) Applications of graph theory to circuits and networks (94C15)

Recommendations

• NP-completeness of slope-constrained drawing of complete graphs
• Complexity of finding non-planar rectilinear drawings of graphs
• The Complexity of Drawing Graphs on Few Lines and Few Planes
• The complexity of drawing graphs on few lines and few planes
• Intractability in graph drawing and geometry: FPT approaches
• scientific article; zbMATH DE number 219263
• scientific article; zbMATH DE number 2170469
• Recognizing tough graphs is NP-hard
• The straight-line RAC drawing problem is NP-hard
• The straight-line RAC drawing problem is NP-hard

Cites work

• scientific article; zbMATH DE number 3882450 (Why is no real title available?)
• scientific article; zbMATH DE number 3752234 (Why is no real title available?)
• scientific article; zbMATH DE number 3793772 (Why is no real title available?)
• A Class Of Abelian Groups
• A linear algorithm for embedding planar graphs using PQ-trees
• Algorithms for drawing graphs: An annotated bibliography
• Efficient Planarity Testing
• Graph theory
• Integer flows
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• The NP-completeness column: An ongoing guide
• The NP-completeness column: An ongoing guide
• The complexity of drawing trees nicely
• Two-Processor Scheduling with Start-Times and Deadlines
• Universality considerations in VLSI circuits

Cited in

(25)

• Unit-length rectangular drawings of graphs
• Free edge lengths in plane graphs
• On the complexity of the Edge Label Placement problem
• HV-planarity: algorithms and complexity
• Computing geometric minimum-dilation graphs is NP-hard
• A note on isosceles planar graph drawing
• The logic engine and the realization problem for nearest neighbor graphs
• On edge-length ratios of partial 2-trees
• On the computational complexity of degenerate unit distance representations of graphs
• Unit-length rectangular drawings of graphs
• Complexity of finding non-planar rectilinear drawings of graphs
• Data-driven graph drawing techniques with applications for conveyor systems
• An Experimental Study on Distance-Based Graph Drawing
• Planar Embeddings of Graphs with Specified Edge Lengths
• Degree-constrained orientations of embedded graphs
• Equilateral spherical drawings of planar Cayley graphs
• Planar straight-line realizations of 2-trees with prescribed edge lengths
• On the Hardness of Orthogonal-Order Preserving Graph Drawing
• On the edge-length ratio of planar graphs
• Testing the planar straight-line realizability of 2-trees with prescribed edge lengths
• NP-completeness of slope-constrained drawing of complete graphs
• Equilateral drawing of 2-connected planar chordal graphs
• On the Edge-Length Ratio of 2-Trees
• Anchored drawings of planar graphs
• Graph Drawing

This page was built for publication: Fixed edge-length graph drawing is NP-hard

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1813977)