Complexity results for three-dimensional orthogonal graph drawing

DOI10.1016/J.JDA.2006.06.002MaRDI QIDQ954967zbMATH OpenOpenAlexFDO

Authors 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) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Recommendations

• Graph Drawing
• The complexity of bendless three-dimensional orthogonal graph drawing
• Three-dimensional orthogonal graph drawing algorithms
• On the complexity of orthogonal compaction
• On bend-minimized orthogonal drawings of planar 3-graphs

Cites work

• scientific article; zbMATH DE number 2123123 (Why is no real title available?)
• scientific article; zbMATH DE number 2080106 (Why is no real title available?)
• scientific article; zbMATH DE number 2080109 (Why is no real title available?)
• scientific article; zbMATH DE number 3291152 (Why is no real title available?)
• A Split&Push Approach to 3D Orthogonal Drawing
• A linear-time algorithm for testing the truth of certain quantified Boolean formulas
• A note on 3D orthogonal drawings with direction constrained edges
• A note on 3D orthogonal graph drawing
• Algorithms for Incremental Orthogonal Graph Drawing in Three Dimensions
• Embedding problems for paths with direction constrained edges.
• Fully dynamic \(3\)-dimensional orthogonal graph drawing
• Graph Drawing
• Graph Drawing
• Graph theory with applications
• Lower Bounds for the Number of Bends in Three-Dimensional Orthogonal Graph Drawings
• Minimising the number of bends and volume in 3-dimensional orthogonal graph drawings with a diagonal vertex layout
• On Embedding a Graph in the Grid with the Minimum Number of Bends
• On the computational complexity of upward and rectilinear planarity testing
• Optimal three-dimensional orthogonal graph drawing in the general position model.
• Rectilinear Graphs and Their Embeddings
• The complexity of minimizing wire lengths in VLSI layouts
• The complexity of theorem-proving procedures
• The logic engine and the realization problem for nearest neighbor graphs
• The realization problem for Euclidean minimum spanning trees is NP-hard
• The techniques of Komolgorov and Bardzin for three-dimensional orthogonal graph drawings
• Three-dimensional orthogonal graph drawing algorithms

Cited in

(7)

• Polygons with Prescribed Angles in 2D and 3D
• The shape of orthogonal cycles in three dimensions
• On the Hardness of Orthogonal-Order Preserving Graph Drawing
• Complexity of higher-degree orthogonal graph embedding in the Kandinsky model
• Polygons with prescribed angles in 2D and 3D
• Graph Drawing
• The complexity of bendless three-dimensional orthogonal graph drawing

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

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