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 , 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.

Item Type: Conference Paper
Additional Information: 10.1007/978-3-540-31843-9_3
Classifications: P Styles > P.600 Poly-line > P.600.300 Mainly Orthogonal
G Algorithms and Complexity > G.210 Bends
Z Theory > Z.250 Geometry
URI: http://gdea.informatik.uni-koeln.de/id/eprint/563

Actions (login required)

View Item View Item