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.

Abstract

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
ID Code:898

Repository Staff Only: item control page

References

Annexstein, F., Baumslag, M., Rosenberg, A.L.: Group action graphs and parallel architectures. SIAM J. Comput. 19(3), 544–569 (1990)

Biedl, T., Shermer, T.C., Whitesides, S., Wismath, S.K.: Bounds for orthogonal 3-D graph drawing. J. Graph Alg. Appl. 3(4), 63–79 (1999)

Biedl, T., Thiele, T., Wood, D.R.:Three-dimensional orthogonal graph drawing with optimal volume. Algorithmica 44(3), 233–255 (2006)

Bonnington, C.P., Little, C.H.C.: The Foundations of Topological Graph Theory. Springer-Verlag, Berlin, Heidelberg, and New York (1995)

Calamoneri, T., Massini, A.: Optimal three-dimensional layout of interconnection networks. Theor. Comput. Sci. 255(1–2), 263–279 (2001)

Closson, M., Gartshore, S., Johansen, J.R., Wismath, S.K.: Fully dynamic 3-dimensional orthogonal graph drawing. J. Graph Alg. Appl. 5(2), 1–34 (2001)

Craft, D.L., White, A.T.: 3-maps. Discrete Math. (2008)

Eades, P., Stirk, C., Whitesides, S.: The techniques of Komolgorov and Bardzin for three-dimensional orthogonal graph drawings. Inf. Proc. Lett. 60(2), 97–103 (1996)

Eades, P., Symvonis, A., Whitesides, S.: Two algorithms for three dimensional orthogonal graph drawing. In: Proc. 4th Int. Symp. on Graph Drawing. Lect. Notes Comput. Sci., vol. 1190, pp. 139–154. Springer-Verlag, Berlin, Heidelberg,New York (1996)

Eppstein, D.: Dynamic generators of topologically embedded graphs. In: Proc. 14th Symp. Discrete Algorithms. pp. 599–608. ACM and SIAM (January 2003)

Eppstein, D.: Isometric diamond subgraphs. In: Proc. 16th Int. Symp. Graph Drawing (2008)

Even, S., Tarjan, R.E.: Computing an st -numbering. Theor. Comput. Sci. 2(3), 339–344 (1976)

Gaiha, P., Gupta, S.K.: Adjacent vertices on a permutohedron. SIAM J. Appl. Math. 32(2), 323–327 (1977)

Kochol, M.: 3-regular non 3-edge-colorable graphs with polyhedral embeddings in orientable surfaces. In: Proc. 16th Int. Symp. Graph Drawing (2008)

Papakostas, A., Tollis, I.G.: Algorithms for incremental orthogonal graph drawing in three dimensions. J. Graph Alg. Appl. 3(4), 81–115 (1999)

Preparata, F.P., Vuillemin, J.: The cube-connected cycles: a versatile network for parallel computation. Commun. ACM 24(5), 300–309 (1981)

Royle, G., Conder, M., McKay, B., Dobscanyi, P.: Cubic symmetric graphs (The Foster Census). Web page http://people.csse.uwa.edu.au/gordon/remote/foster/ (2001)

Wood, D.R.: An algorithm for three-dimensional orthogonal graph drawing. In: Proc. 6th Int. Symp. Graph Drawing. Lect. Notes Comput. Sci., vol. 1547, pp. 332–346. Springer-Verlag, Berlin, Heidelberg, and New York (1998)

Wood, D.R.: Bounded degree book embeddings and three-dimensional orthogonal graph drawing. In: Proc. 9th Int. Symp. Graph Drawing. Lect. Notes Comput. Sci., vol. 2265, pp. 312–327. Springer-Verlag, Berlin, Heidelberg, and New York (2002)

Wood, D.R.: Optimal three-dimensional orthogonal graph drawing in the general position model. Theor. Comput. Sci. 299(1–3), 151–178 (2003)