# The Complexity of Bendless Three-Dimensional Orthogonal Graph Drawing

@article{Eppstein2013TheCO, title={The Complexity of Bendless Three-Dimensional Orthogonal Graph Drawing}, author={David Eppstein}, journal={J. Graph Algorithms Appl.}, year={2013}, volume={17}, pages={35-55} }

We consider embeddings of 3-regular graphs into 3-dimensional Cartesian coordinates, in such a way that two vertices are adjacent if and only if two of their three coordinates are equal (that is, if they lie on an axis-parallel line) and such that no three points lie on the same axis-parallel line; we call a graph with such an embedding an xyz graph}. We describe a correspondence between xyz graphs and face-colored embeddings of the graph onto two-dimensional manifolds, and we relate… Expand

#### Figures and Topics from this paper

#### 2 Citations

Steinitz Theorems for Simple Orthogonal Polyhedra

- Mathematics, Computer Science
- J. Comput. Geom.
- 2014

We define a simple orthogonal polyhedron to be a three-dimensional polyhedron with the topology of a sphere in which three mutually-perpendicular edges meet at each vertex.By analogy to Steinitz's… Expand

Upward planar drawings with two slopes

- Computer Science
- ArXiv
- 2021

It is shown how to draw an upward planar phylogenetic network with two slopes such that all leaves lie on a horizontal line using SPQR-trees and the notion of upward spirality. Expand

#### References

SHOWING 1-10 OF 60 REFERENCES

Graph and map isomorphism and all polyhedral embeddings in linear time

- Mathematics, Computer Science
- STOC
- 2008

A linear time algorithm to test the graph isomorphism of two graphs, one of which admits an embedding of face-width at least 3 into S, improves a previously known algorithm and is the first algorithm for which the degree of polynomial in the time complexity does not depend on g. Expand

Bounded Degree Book Embeddings and Three-Dimensional Orthogonal Graph Drawing

- Mathematics, Computer Science
- Graph Drawing
- 2001

A Las Vegas algorithm is presented which produces a book embedding of G with O(∣V ∣3/2∣E∣) volume, and single-row drawings with two bends per edge and the same volume, establishing improved bounds for the volume of 3-D orthogonal graph drawings. Expand

Optimal three-dimensional orthogonal graph drawing in the general position model

- Computer Science, Mathematics
- Theor. Comput. Sci.
- 2003

An algorithm for producing general position drawings with an average of at most 2 2/7 bends per edge is presented, which is the best known upper bound on the number of bends in three-dimensional orthogonal drawings, and is optimal for general position Drawings of K7. Expand

Fully Dynamic 3-Dimensional Orthogonal Graph Drawing

- Computer Science
- Graph Drawing
- 1999

A layout scheme that draws any graph with n vertices of maximum degree 6, using at most 6 bends per edge and in a volume of O(n2), allowing both insertion and deletion of vertices and edges, while maintaining the volume and bend bounds. Expand

Three-Dimensional Orthogonal Graph Drawing with Optimal Volume

- Mathematics, Computer Science
- Algorithmica
- 2005

Three-dimensional orthogonal drawings are studied and lower bounds for three scenarios are provided, where the vertices have a bounded aspect ratio, the surfaces of vertices are proportional to their degrees, and without any restrictions. Expand

3-Regular Non 3-Edge-Colorable Graphs with Polyhedral Embeddings in Orientable Surfaces

- Mathematics, Computer Science
- Graph Drawing
- 2008

A negative solution of Grunbaum's conjecture is presented, showing that for each orientable surface of genus at least 5, there exists a 3-regular non 3-edge-colorable graph with a polyhedral embedding in the surface. Expand

Algorithms for Incremental Orthogonal Graph Drawing in Three Dimensions

- Mathematics, Computer Science
- J. Graph Algorithms Appl.
- 1999

Two algorithms for orthogonal graph drawing in three dimensional space are presented that guarantee no crossings and can be used under an interactive setting (i.e., vertices arrive and enter the drawing on-line), as well. Expand

Steinitz theorems for orthogonal polyhedra

- Computer Science, Mathematics
- SCG
- 2010

The graphs of simple orthogonal polyhedra are exactly the 3-regular bipartite planar graphs in which the removal of any two vertices produces at most two connected components. Expand

On Rectilinear Drawing of Graphs

- Mathematics, Computer Science
- Graph Drawing
- 2009

This paper presents a linear time fixed-parameter tractable algorithm to test whether a degree-4 graph has a rectilinear drawing, and shows that the problem is NP-hard for the graphs that consist of 4-cycle blocks connected by single edges, as well as the case where each vertex has degree 2 or 4. Expand

Two Algorithms for Three Dimensional Orthogonal Graph Drawing

- Mathematics, Computer Science
- Graph Drawing
- 1996

Two algorithms for constructing 3-dimensional, intersection-free orthogonal grid drawings of n vertex graphs of maximum degree 6 are designed and initiate the study of bend/bounding box trade-off issues for3-dimensional grid drawings. Expand