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.

Abstract

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
ID Code:563

Repository Staff Only: item control page

References

T. Biedl. New lower bounds for orthogonal drawings. J. Graph Algorithms Appl., 2(7):1-31, 1998.

T. Biedl. Relating bends and size in orthogonal graph drawings. Inform. Process. Lett., 65(2):111-115, 1998.

T. Biedl and G. Kant. A better heuristic for orthogonal graph drawings. Comput. Geom., 9(3):159-180, 1998.

P. Eades, A. Symvonis, and S. Whitesides. Three-dimensional orthogonal graph drawing algorithms. Discrete Appl. Math., 103(1-3):55-87, 2000.

S. Even and R. E. Tarjan. Computing an st-numbering. Th. Comput. Sci., 2:339-344, 1976.

G. Kant. Hexagonal grid drawings. In Graph-theoretic Concepts in Computer Science, vol. 657 of Lect. Notes in Comput. Sci., pages 263-276. Springer, 1993.

A. Lempel, S. Even, and I. Cederbaum. An algorithm for planarity testing of graphs. In Theory of Graphs (Internat. Sympos., Rome, 1966), pages 215-232. New York, 1967.

A. Papakostas and I. G. Tollis. Algorithms for area-efficient orthogonal drawings. Comput. Geom., 9(1-2):83-110, 1998.

J. Storer. On minimla-node-cost planar embeddings. Networks, 14(2):181-212, 1984.

R. Tamassia. On embedding a graph in the grid with the minimum number of bends. SIAM J. Comput., 16(3):421-444, 1987.

R. Tamassia and I. G. Tollis. Planar grid embedding in linear time. IEEE Transactions on Circuits and Systems, 36(9):1230-1234, 1989.

I. Tollis. Wiring layouts in the tri-hexagonal grid. Constraints, 3(1):87-120, 1998.

D.R. Wood. An algorithm for three-dimensional orthogonal graph drawing. In Graph Drawing, volume 1547 of Lecture Notes in Comput. Sci., pages 332-346. Springer, 1998.

D. R. Wood. Lower bounds for the number of bends in three-dimensional orthogonal graph drawings. J. Graph Algorithms Appl., 7(1):33-77, 2003.

D. R. Wood. Optimal three-dimensional orthogonal graph drawing in the general position model. Th. Comput. Sci., 299(1-3):151-178, 2003.