1-bend 3-D orthogonal box-drawings: Two open problems solved
This paper studies three-dimensional drawings of graphs where vertices are represented by axis-parallel boxes and edges are represented by disjoint routes with at most one bend in a three-dimensional rectangular grid. It is known that such box-drawings without bends are not always possible. The two open problems on these 1-bend box-drawings which are solved in the paper are the following: (1) Does every 1-bend drawing of \(K_n\) have volume \(\Omega(n^3)\)? (2) Is there a 1-bend drawing of \(K_n\) where in addition the vertices are represented by cubes with surface \(O(n)\)? The paper answers both questions in the negative and provides other results for 1-bend drawings of graphs without loops and multiple edges. Furthermore, other bounds are obtained for 1-bend drawings of the Ramanujan graph.
- The complexity of bendless three-dimensional orthogonal graph drawing
- The Topology of Bendless Three-Dimensional Orthogonal Graph Drawing
- On bend-minimized orthogonal drawings of planar 3-graphs
- scientific article; zbMATH DE number 1953108
- scientific article; zbMATH DE number 2080105
- Lower Bounds for the Number of Bends in Three-Dimensional Orthogonal Graph Drawings
- A note on 3D orthogonal drawings with direction constrained edges
- scientific article; zbMATH DE number 1500687
- Three-Dimensional 1-Bend Graph Drawings
- Computing orthogonal drawings with the minimum number of bends
This page was built for publication: 1-bend 3-D orthogonal box-drawings: Two open problems solved
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2724198)
