Bounded Degree Book Embeddings and Three-Dimensional Orthogonal Graph Drawing

Wood, David R. (2002) Bounded Degree Book Embeddings and Three-Dimensional Orthogonal Graph Drawing. In: Graph Drawing 9th International Symposium, GD 2001, September 23-26, 2001, Vienna, Austria , pp. 312-327 (Official URL: http://dx.doi.org/10.1007/3-540-45848-4_25).

Full text not available from this repository.

Abstract

A book embedding of a graph consists of a linear ordering of the vertices along a line in 3-space (the spine), and an assignment of edges to half-planes with the spine as boundary (the pages), so that edges assigned to the same page can be drawn on that page without crossings. Given a graph G=(V,E), let f:V\rightarrow\mathbb {N} be a function such that 1\leq f(v)\leq\deg(v). We present a Las Vegas algorithm which produces a book embedding of G with O{\sqrt{\vert E\vert\cdot\max_v\lceil{\deg(v)/f(v)}\rceil}} pages, such that at most f(v) edges incident to a vertex v are on a single page. This algorithm generalises existing results for book embeddings. We apply this algorithm to produce 3-D orthogonal drawings with one bend per edge and O{\vert V\vert^{3/2}\vert E\vert} volume, and single-row drawings with two bends per edge and the same volume. In the produced drawings each edge is entirely contained in some Z-plane; such drawings are without so-called cross-cuts, and are particularly appropriate for applications in multilayer VLSI. Using a different approach, we achieve two bends per edge with O{\vert V\vert\vert E\vert} volume but with cross-cuts. These results establish improved bounds for the volume of 3-D orthogonal graph drawings.

Item Type:Conference Paper
Additional Information:10.1007/3-540-45848-4_25
Classifications:G Algorithms and Complexity > G.210 Bends
P Styles > P.600 Poly-line > P.600.700 Orthogonal
P Styles > P.060 3D
ID Code:493

Repository Staff Only: item control page

References

Proc. EuroConference on Combinatorics, Graph Theory and Applications (COMB '01), Electronic Notes in discrete Mathematics, to appear.

Agarwal, A., Klawe, M., Shor, P., Multi-layer grid embeddings for VLSI, Algorithmica 6, (1991), 129-151.

T. Biedl. 1-bend 3-D orthogonal box-drawings: Two open problems solved. J. Graph Algorithms Appl., 5(3):1-15, 2001.

T. Biedl, T. Thiele, and D.R. Wood. Three-dimensional orthogonal graph drawing with optimal volume. In J. Marks, editor, Proc. Graph Drawing: 8th International Symposium (GD '00), vol. 1984 of LNCS, pages 284-295. Springer, 2001.

T. C. Biedl. Three approaches to 3D-orthogonal box-drawings. In Whitesides, editor, Proc. Graph Drawing: 6th International Symp. (GD '98), volume 1547 of Lecture Notes in Comput. Sci., pages 30-43. Springer, 1998.

T. Biedl and M. Kaufmann. Area-efficient static and incremental graph drawings. In 5th European Symposium on Algorithms, vol. 1284 of LNCS, pages 37-52. Springer-Verlag, 1997.

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

F.R.K. Chung, F.T. Leighton, and A.L. Rosenberg. Embedding graphs in books: a layout problem with applications to VLSI design. SIAM J. Algebraic Discrete Methods, 8(1):33-58, 1987.

R.P. Dilworth. A decomposition theorem for partially ordered sets. Ann. of Math.(2), 51:161-166, 1950.

S.L. Hakimi and O. Kariv. A generalization of edge-coloring in graphs. J. Graph Theory, 10(2):139-154, 1986.

L.S. Heath and A.L. Rosenberg. Laying out graphs using queues. SIAM J. Comput., 21(5):927-958, 1992.

E.S. Kuh, T. Kashiwabara, and T. Fujisawa. On optimum single-row routing. IEEE Trans. Circuits and Systems, 26(6):361-368, 1979.

S.M. Malitz. Genus g graphs have pagenumber O(\sqrt{g}). J. Algorithms, 17(1):85-109, 1994.

S.M. Malitz. Graphs with E edges have pagenumber O(\sqrt{E}). J. Algorithms . 17(1):71-84, 1994.

F. Malucceli and S. Nicoloso. Optimal partition of a bipartite graph into noncrossing matchings. In [1].

R. Tarjan. Sorting using networks of queues and stacks. J. Assoc. Comput. mach., 19:341-346, 1972.

V.G. Vizing. On an estimate of the chromatic class of a p-graph. diskret. Analiz No., 3:25-30, 1964.

D. R. Wood. Three-dimensional orthogonal graph drawings with one bend per edge. Submitted. See Three-Dimensional Orthogonal Graph Drawing. PH.D. thesis, School of Computer Science and Software Engineering, Monash University, Australia, 2000.

D.R. Wood. Geometric thickness in a grid of linear area. In: Proc. EuroConference on Combinatorics, Graph Theory and Applications (COMB '01), Electronic Notes in discrete Mathematics, to appear.