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. In: Symposium on Graph Drawing, GD '96, September 18-20, 1996 , pp. 53-62(Official URL: http://dx.doi.org/10.1007/3-540-62495-3_37).

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 leas1. t \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
Additional Information: 10.1007/3-540-62495-3_37
Classifications: G Algorithms and Complexity > G.999 Others
P Styles > P.060 3D
URI: http://gdea.informatik.uni-koeln.de/id/eprint/64

Actions (login required)

View Item View Item