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, Heraklion, Crete, Greece , pp. 78-89 (Official URL: http://dx.doi.org/10.1007/978-3-642-00219-9_9).
Full text not available from this repository.
We deﬁne 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 ).
Repository Staff Only: item control page