Complexity results for three-dimensional orthogonal graph drawing

DOI10.1016/j.jda.2006.06.002zbMath1152.68046OpenAlexW2060444627MaRDI QIDQ954967

Maurizio Patrignani

Publication date: 18 November 2008

Published in: Journal of Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jda.2006.06.002

zbMATH Keywords

computational complexitythree-dimensional graph drawingorthogonal layout

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (3)

Polygons with Prescribed Angles in 2D and 3D ⋮ The shape of orthogonal cycles in three dimensions ⋮ Polygons with Prescribed Angles in 2D and 3D

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The complexity of minimizing wire lengths in VLSI layouts
• A linear-time algorithm for testing the truth of certain quantified Boolean formulas
• The logic engine and the realization problem for nearest neighbor graphs
• The techniques of Komolgorov and Bardzin for three-dimensional orthogonal graph drawings
• Three-dimensional orthogonal graph drawing algorithms
• Embedding problems for paths with direction constrained edges.
• Optimal three-dimensional orthogonal graph drawing in the general position model.
• Minimising the number of bends and volume in 3-dimensional orthogonal graph drawings with a diagonal vertex layout
• The realization problem for Euclidean minimum spanning trees is NP-hard
• A note on 3D orthogonal drawings with direction constrained edges
• A note on 3D orthogonal graph drawing
• Fully Dynamic 3-Dimensional Orthogonal Graph Drawing
• On the Computational Complexity of Upward and Rectilinear Planarity Testing
• Rectilinear Graphs and Their Embeddings
• On Embedding a Graph in the Grid with the Minimum Number of Bends
• Lower Bounds for the Number of Bends in Three-Dimensional Orthogonal Graph Drawings
• Algorithms for Incremental Orthogonal Graph Drawing in Three Dimensions
• A Split&Push Approach to 3D Orthogonal Drawing
• The complexity of theorem-proving procedures
• Graph Drawing
• Graph Drawing

This page was built for publication: Complexity results for three-dimensional orthogonal graph drawing