Logo

Login | Create Account

Drawing 2-, 3- and 4-colorable Graphs in O(n²) Volume

Calamoneri, Tiziana and Sterbini, Andrea (1997) Drawing 2-, 3- and 4-colorable Graphs in O(n²) Volume. [Conference Paper]

Full text not available from this repository.

Abstract

A Fary grid drawing of a graph is a drawing on a three-dimensional grid such that vertices are placed at integer coordinates and edges are straight-lines such that no edge crossings are allowed. In this paper it is proved that each k-colorable graph (k>=2) needs at least \Omega (n^(3/2)) volume to be drawn. Furthermore, it is shown how to draw 2-, 3- and 4-colorable graphs in a Fary grid fashion in O(n²) volume.

Item Type:Conference Paper
Classifications:G Algorithms and Complexity > G.999 Others
P Styles > P.060 3D
ID Code:64
Deposited By:Arnopolina, Galina
Deposited On:20 Oct 2004
Last Modified:18 Sep 2008 13:08

Repository Staff Only: item control page

References

1. R. F. Cohen, P. Eades, T. Lin and F. Ruskey: Three-dimensional graph drawing, In Proc. GD '94, LNCS 894, pp. 1-11, 1994.

2. I. Fary: On straight lines representations of planar graphs, Acta Sci. Math. Szeged, 11, pp. 229-233, 1948.

3. G. Frank, D. Hui and C. Ware: Visualizing object oriented software in three dimensions, In Proc. CASCON, 1993.

4. J. MacKinley, G. Robertson and S. Card: Cone trees: Animated 3d visualization of hierarchical information, In Proc. SIGCHI Conf. on Human Factors in Computing, pp. 189-194, 1991.

5. P. Reid: Dynamic interactive display of complex data structures, In Graphics Tools for Software Engineers, pp. 62-70, Cambridge, 1989.

6. O. Tversky, S. Snibbe and R. Zeleznik: Cone trees in the uga graphics system: suggestions of a more robust visualization tool, Technical Report CS-93-07, Brown University, 1993.

GDEA is powered by EPrints 3 which is developed by the School of Electronics and Computer Science at the University of Southampton. More information and software credits.