Complexity results for three-dimensional orthogonal graph drawing

DOI10.1016/J.JDA.2006.06.002zbMATH Open1152.68046OpenAlexW2060444627MaRDI QIDQ954967FDOQ954967

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

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

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)

Cites Work

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

Cited In (7)

• The shape of orthogonal cycles in three dimensions
• On the Hardness of Orthogonal-Order Preserving Graph Drawing
• Graph Drawing
• Complexity of higher-degree orthogonal graph embedding in the Kandinsky model
• Polygons with Prescribed Angles in 2D and 3D
• Polygons with Prescribed Angles in 2D and 3D
• 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)