On the Hardness of Orthogonal-Order Preserving Graph Drawing

DOI10.1007/978-3-642-00219-9_25MaRDI QIDQ3611858zbMATH OpenOpenAlexFDO

Authors Ulrik Brandes, Barbara Pampel

Publication date 3 March 2009

Published in Graph Drawing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-00219-9_25

Mathematics Subject Classification ID

Graph representations (geometric and intersection representations, etc.) (05C62) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Recommendations

• Hardness of approximate compaction for nonplanar orthogonal graph drawings
• Efficient orthogonal drawings of high degree graphs
• Complexity results for three-dimensional orthogonal graph drawing
• scientific article; zbMATH DE number 219263
• Computing and Combinatorics
• Lower bounds for planar orthogonal drawings of graphs
• Graph Drawing
• A better heuristic for orthogonal graph drawings
• The DFS-heuristic for orthogonal graph drawing
• The complexity of bendless three-dimensional orthogonal graph drawing

Cites work

• A User Study in Similarity Measures for Graph Drawing
• Algorithms and Computation
• Fixed edge-length graph drawing is NP-hard
• Graph Drawing
• Graph Drawing
• scientific article; zbMATH DE number 2185597 (Why is no real title available?)
• scientific article; zbMATH DE number 4026646 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Near-linear time approximation algorithms for curve simplification
• Path Simplification for Metro Map Layout
• Trees with Convex Faces and Optimal Angles

Cited in

(4)

• On \(d\)-regular schematization of embedded paths
• scientific article; zbMATH DE number 2080110 (Why is no real title available?)
• Orthogonal-ordering constraints are tough
• The DFS-heuristic for orthogonal graph drawing

This page was built for publication: On the Hardness of Orthogonal-Order Preserving Graph Drawing

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