Path-Width and Three-Dimensional Straight-Line Grid Drawings of Graphs

Dujmovic, Vida and Morin, Pat and Wood, David R. (2002) Path-Width and Three-Dimensional Straight-Line Grid Drawings of Graphs. In: Graph Drawing 10th International Symposium, GD 2002, August 26-28, 2002, Irvine, CA, USA , pp. 42-53 (Official URL: http://dx.doi.org/10.1007/3-540-36151-0_5).

Full text not available from this repository.

Abstract

We prove that every n-vertex graph G with path-width pw(G) has a three-dimensional straight-line grid drawing with O(pw(G)² *n) volume. Thus for graphs with bounded path-width the volume is O(n), and it follows that for graphs with bounded tree-width, such as series-parallel graphs, the volume is O(n log² n). No better bound than O(n²) was previously known for drawings of series-parallel graphs. For planar graphs we obtain three-dimensional drawings with O(n²) volume and O(\sqrt{n}) aspect ratio, whereas all previous constructions with O(n²) volume have \Theta(n) aspect ratio.

Item Type:Conference Paper
Additional Information:10.1007/3-540-36151-0_5
Classifications:P Styles > P.720 Straight-line
Z Theory > Z.250 Geometry
G Algorithms and Complexity > G.070 Area / Edge Length
P Styles > P.060 3D
ID Code:268

Repository Staff Only: item control page

References

H.L. BODLAENDER, A linear-time algorithm for finding tree-decompositions of small treewidth. SIAM J. Comput., 25(6):1305-1317, 1996.

H.L. BODLAENDER, A partial k-arboretum of graphs with bounded treewidth. Theoret. Comput. Sci., 209(1-2):1-45, 1998.

F.J. BRANDENBURG, ed., Proc. International Symp. on Graph Drawing (GD '95), vol. 1027 of Lecture Notes in Comput. Sci., Springer, 1996.

I. BRUß AND A. FRICK, Fast interactive 3D graph visualization. In [3], pp. 99-110.

T. CALAMONERI AND A. STERBINI, 3D straight-line grid drawing of 4-colorable graphs. Inform. Process. Lett., 63(2):97-102, 1997.

K. CHILAKAMARRI, N. DEAN, AND M. LITTMAN, Three-dimensional Tutte embedding. In Proc. 26th Southeastern International Conf. on Combinatorics, Graph Theory and Computing, vol. 107 of Cong. Numer., pp. 129-140, 1995.

M. CHROBAK, M. GOODRICH, AND R. TAMASSIA, Convex drawings of graphs in two and three dimensions. In Proc. 12th Annual ACM Symp. on Comput. Geom., pp. 319-328, 1996.

R.F. COHEN, P. EADES, T. LIN, AND F. RUSKEY, Three-dimensional graph drawing. Algorithmica, 17(2):4199-208, 1996.

I.F. CRUZ AND J.P. TWAROG, 3D graph drawing with simulated annealing. In [3], pp. 162-165.

H. DE FRAYSSEIX, J. PACH, AND R. POLLACK, How to draw a planar graph on a grid. Combinatorica, 10(1):41-51, 1990.

E. DI GIACOMO, G. LIOTTA, AND S. WISMATH, Drawing series-parallel graphs on a box. In S. WISMATH, ed., Proc. 14th Canadian Conf. on Computational Geometry (CCCG'02), The University of Lethbridge, Canada 2002.

R.G. DOWNEY AND M.R. FELLOWS, Parameterized complexity. Springer, 1999.

V. DUJMOVIC, M. FELLOWS, M. HALLETT, M. KITCHING, G. LIOTTA, C. McCARTIN, N. NISHIMURA, P. RAGDE, F. ROSEMAND, M. SUDERMAN, S. WHITESIDES, AND D.R. WOOD, On the parameterized complexity of layered graph drawing. In F. MEYER AUF DER HEIDE, ed., Proc. 5th Annual European Symp. on Algorithms (ESA '01), vol. 2161 of Lecture Notes in Comput. Sci., pp. 488-499, Springer, 2001.

V. DUJMOVIC AND D.R. WOOD, Tree-partitions of k-trees with applications in graph layout. Tech. Rep. TR-02-03, School of Computer Science, Carleton University, Ottawa, Canada, 2002.

P. EADES AND P. GARVAN, Drawing stressed planar graphs in three dimensions. In [3], pp. 212-223.

P. ERDÖS, Appendix. In K.F. ROTH, On a problem of Heilbronn. J. London Math. Soc., 26:198-204, 1951.

S. FELSNER, S. WISMATH, AND G. LIOTTA, Straight-line drawings on restricted integer grids in two and three dimensions. In [28], pp. 328-342.

A. GARG, R. TAMASSIA, AND P. VOCCA, Drawing with colors. In J. DIAZ AND M. SERNA, eds., Proc. 4th Annual European Symp. on Algorithms (ESA '96), vol. 1136 of Lecture Notes in Comput. Sci., pp.12-26, Springer, 1996.

A. GUPTA AND N. NISHIMURA, Sequential and parallel algorithms for embedding problems on classes of partial k-trees. In Proc. 4th Scandinavian Workshop on Algorithm Theory (SWAT '94), vol. 824 of Lecture Notes in Comput. Sci., pp. 172-182, Springer, 1984.

A. GUPTA, N. NISHIMURA, A. PROSKUROWSKI, AND P. RAGDE, Embeddings of k-connected graphs of pathwidth k. In M.M. HALLDORSSON, ed., Proc. 7th Scandinavian Workshop on Algorithm Theory (SWAT '00), vol. 1851 of Lecture Notes in Comput. Sci., pp. 111-124, Springer, 2000.

P. HLINENY, Crossing-critical graphs and path-width. In: P. MUTZEL, M. JÜNGER, AND S. LEIPERT, eds., Proc. 9th International Symp. on Graph Drawing (GD '01), vol. 2265 of Lecture Notes in Comput. Sci., pp. 102-114.

S.-H. HONG, Drawing graphs symmetrically in three dimensions. In [28], pp. 189-204.

S.-H. HONG AND P. EADES, An algorithm for finding three dimensional symmetry in series parallel digraphs. In D. LEE AND S.-H. TENG, eds., Proc. 11th International Conf. on Algorithms and Computation (ISAAC '00), vol. 1969 of Lecture Notes in Comput. Sci., pp. 266-277, Springer, 2000.

S.-H. HONG AND P. EADES, An algorithm for finding three dimensional symmetry in trees. In J. MARKS, ed., Proc. 8th International Symp. on Graph Drawing (GD '00), vol. 1984 of Lecture Notes in Comput. Sci., pp. 360-371, Springer, 2001.

S.-H. HONG, P. EADES, A. QUIGLEY, AND S.-H. LEE, Drawing algorithms for series-parallel digraphs in two and three dimensions. In S. WHITESIDES, ed., Proc. 6th International Symp. on Graph Drawing (GD '98), vol. 1547 of Lecture Notes in Comput. Sci., pp. 198-209, Springer, 1998.

F.T. LEIGHTON AND A.L. ROSENBERG, Three-dimensional circuit layouts. SIAM J. Comput., 15(3):793-813, 1986.

B. MONIEN, F. RAMME, AND H. SALMEN, A parallel simulated annealing algorithm for generating 3D layouts of undirected graphs. In [3], pp. 396-408.

P. MUTZEL, M. JÜNGER, AND S. LEIPERT, eds., Proc. 9th International Symp. on Graph Drawing (GD '01), vol. 2265 of Lecture Notes in Comput. Sci., pp. 198-209, Springer, 2002.

D.I. OSTRY, Some Three-Dimensional Graph Drawing Algorithms. Master's thesis, Department of Computer Science and Software Engineering, The University of Newcastle, Australia, 1996.

J. PACH, T. THIELE, AND G. TÓTH, Three-dimensional grid drawings of graphs. In G. DI BATTISTA, ed., Proc. 5th International Symp. on Graph Drawing (GD '97), vol. 1353 of Lecture Notes in Comput. Sci., pp. 47-51, Springer, 1998.

Z. PENG, Drawing Graphs of Bounded Treewidth/Pathwidth. Master's thesis, Department of Computer Science, University of Auckland, New Zealand, 2001.

T. PORANEN, A new algorithm for drawing series-parallel digraphs in 3D. Tech. Rep. A-2000-16, Dept. of Computer and Information Sciences, University of Tampere, Finland, 2000.

W. SCHNYDER, Planar graphs and poset dimension. Order, 5(4):323-343, 1989.

M. THORUP, All structured programs have small tree-width and good register allocation. Information and Computation, 142(2):159-181, 1998.

C. WARE AND G. FRANCK, Viewing a graph in a virtual reality display is three times as good as a 2D diagram. in A.L. AMBLER and T.D. KIMURA, eds., Proc. IEEE Symp. Visual Languages (VL '94), pp. 182-183, IEEE, 1994.

C. WARE, D. HUI, AND G. FRANCK, Visualizing object oriented software in three dimensions. In Proc. IBM Centre for Advanced Studies Conf. (CASCON '93), pp. 1-11, 1993.

R. WEISKIRCHER, Drawing planar graphs. In M. KAUFMANN AND D. WAGNER, eds., Drawing Graphs: Methods and Models, vol. 2025 of Lecture Notes in Comput. Sci., pp. 23-45, Springer, 2001.

D.R. WOOD, Queue layouts, tree-width, and three-dimensional graph drawing. Tech. Rep. TR-02-02 (revised), School of Computer Science, Carleton University, Ottawa, Canada, August, 2002.