Canonical Ordering for Triangulations on the Cylinder, with Applications to Periodic Straight-Line Drawings

Castelli Aleardi, Luca and Devillers, Olivier and Fusy, Éric (2013) Canonical Ordering for Triangulations on the Cylinder, with Applications to Periodic Straight-Line Drawings. In: 20th International Symposium, GD 2012, September 19-21, 2012, Redmond, WA, USA , pp. 376-387 (Official URL: http://link.springer.com/chapter/10.1007/978-3-642-36763-2_34).

Full text not available from this repository.

Abstract

We extend the notion of canonical orderings to cylindric triangulations. This allows us to extend the incremental straight-line drawing algorithm of de Fraysseix, Pach and Pollack to this setting. Our algorithm yields in linear time a crossing-free straight-line drawing of a cylindric triangulation G with n vertices on a regular grid $ℤ/wℤ×[0..h]$, with $w ≤ 2n$ and $h ≤ n(2d + 1)$, where d is the (graph-) distance between the two boundaries. As a by-product, we can also obtain in linear time a crossing-free straight-line drawing of a toroidal triangulation with n vertices on a periodic regular grid$ ℤ/wℤ×ℤ/hℤ$, with $w ≤ 2n$ and $h ≤ 1 + n(2c + 1)$, where c is the length of a shortest non-contractible cycle. Since $c≤sqrt{2n}$, the grid area is $O(n^{5/2})$. Our algorithms apply to any triangulation (whether on the cylinder or on the torus) that have no loops nor multiple edges in the periodic representation.

Item Type:Conference Paper
Additional Information:10.1007/978-3-642-36763-2_34
Classifications:G Algorithms and Complexity > G.280 Canonical Ordering
P Styles > P.720 Straight-line
ID Code:1326

Repository Staff Only: item control page

References

Albertson, M.O., Hutchinson, J.P.: On the independence ratio of a graph. J. Graph. Theory 2, 1–8 (1978)

Bonichon, N., Gavoille, C., Labourel, A.: Edge partition of toroidal graphs into forests in linear time. In: ICGT, vol. 22, pp. 421–425 (2005)

Brehm, E.: 3-orientations and Schnyder 3-trees decompositions, Master’s thesis, FUB (2000)

Castelli-Aleardi, L., Fusy, E., Lewiner, T.: Schnyder woods for higher genus triangulated surfaces, with applications to encoding. Discr. & Comp. Geom. 42(3), 489–516 (2009)

Chambers, E., Eppstein, D., Goodrich, M., Loffler, M.: Drawing graphs in the plane with a prescribed outer face and polynomial area. JGAA 16(2), 243–259 (2012)

de Fraysseix, H., Pach, J., Pollack, R.: How to draw a planar graph on a grid. Combinatorica 10(1), 41–51 (1990)

Duncan, C., Goodrich, M., Kobourov, S.: Planar drawings of higher-genus graphs. Journal of Graph Algorithms and Applications 15, 13–32 (2011)

Gonçalves, D., Lévêque, B.: Toroidal maps: Schnyder woods, orthogonal surfaces and straight-line representations arXiv:1202.0911 (2012)

Gortler, S.J., Gotsman, C., Thurston, D.: Discrete one-forms on meshes and applications to 3D mesh parameterization. Computer Aided Geometric Design 23(2), 83–112 (2006)

Kant, G.: Drawing planar graphs using the canonical ordering. Algorithmica 16(1), 4–32 (1996)

Kocay, W., Neilson, D., Szypowski, R.: Drawing graphs on the torus. Ars Combinatoria 59, 259–277 (2001)

Mohar, B.: Straight-line representations of maps on the torus and other flat surfaces. Discrete Mathematics 15, 173–181 (1996)

Mohar, B., Rosenstiehl, P.: Tessellation and visibility representations of maps on the torus. Discrete & Comput. Geom. 19, 249–263 (1998)

Schnyder, W.: Embedding planar graphs on the grid. In: SODA, pp. 138–148 (1990)

Zitnik, A.: Drawing graphs on surfaces. SIAM J. Disc. Math. 7(4), 593–597 (1994)