The Topology of Bendless Three-Dimensional Orthogonal Graph Drawing

Eppstein, David (2009) The Topology of Bendless Three-Dimensional Orthogonal Graph Drawing. In: Graph Drawing 16th International Symposium, GD 2008, September 21- 24, 2008 , pp. 78-89(Official URL:

Full text not available from this repository.


We define an xyz graph to be a spatial embedding of a 3-regular graph such that the edges at each vertex are mutually perpendicular and no three points lie on an axis-parallel line. We describe an equivalence between xyz graphs and 3-face-colored polyhedral maps, under which bipartiteness of the graph is equivalent to orientability of the map. We show that planar graphs are xyz graphs if and only if they are bipartite, cubic, and three-connected. It is NP-complete to recognize xyz graphs, but we show how to do this in time O(n2n/2 ).

Item Type: Conference Paper
Additional Information: 10.1007/978-3-642-00219-9_9
Classifications: M Methods > M.800 Topology-shape-metrics
G Algorithms and Complexity > G.490 Embeddings
P Styles > P.060 3D

Actions (login required)

View Item View Item