Hexagonal Grid Drawings: Algorithms and Lower Bounds
Aziza, Shabnam and Biedl, Therese (2004) Hexagonal Grid Drawings: Algorithms and Lower Bounds. In: Graph Drawing 12th International Symposium, GD 2004, September 29-October 2, 2004, New York, NY, USA , pp. 18-24 (Official URL: http://dx.doi.org/10.1007/978-3-540-31843-9_3).
Full text not available from this repository.
We study drawings of graphs of maximum degree six on the hexagonal (triangular) grid, with the main focus of keeping the number of bends small. We give algorithms that achieve 3.5n + 3.5 bends for all simple graphs. We also prove optimal lower bounds on the number of bends for K_7, and give asymptotic lower bounds for graph classes of varying connectivity. Research supported by NSERC. These results appeared as part of the MMath thesis of the first author at University of Waterloo.
Repository Staff Only: item control page