The Topology of Bendless ThreeDimensional Orthogonal Graph DrawingEppstein, David (2009) The Topology of Bendless ThreeDimensional Orthogonal Graph Drawing. In: Graph Drawing 16th International Symposium, GD 2008, September 21 24, 2008 , pp. 7889(Official URL: http://dx.doi.org/10.1007/9783642002199_9). Full text not available from this repository.
Official URL: http://dx.doi.org/10.1007/9783642002199_9
AbstractWe deﬁne an xyz graph to be a spatial embedding of a 3regular graph such that the edges at each vertex are mutually perpendicular and no three points lie on an axisparallel line. We describe an equivalence between xyz graphs and 3facecolored 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 threeconnected. It is NPcomplete to recognize xyz graphs, but we show how to do this in time O(n2n/2 ).
Actions (login required)
