# Canonical ordering for graphs on the cylinder, with applications to periodic straight-line drawings on the flat cylinder and torus

2 GAMBLE - Geometric Algorithms and Models Beyond the Linear and Euclidean realm
Inria Nancy - Grand Est, LORIA - ALGO - Department of Algorithms, Computation, Image and Geometry
Abstract : We extend the notion of canonical ordering (initially developed for planar triangulations and 3-connected planar maps) to cylindric (essentially simple) triangulations and more generally to cylindric (essentially internally) $3$-connected maps. This allows us to extend the incremental straight-line drawing algorithm of de Fraysseix, Pach and Pollack (in the triangulated case) and of Kant (in the $3$-connected case) to this setting. Precisely, for any cylindric essentially internally $3$-connected map $G$ with $n$ vertices, we can obtain in linear time a periodic (in $x$) straight-line drawing of $G$ that is crossing-free and internally (weakly) convex, on a regular grid $\mathbb{Z}/w\mathbb{Z}\times[0..h]$, with $w\leq 2n$ and $h\leq n(2d+1)$, where $d$ is the face-distance between the two boundaries. This also yields an efficient periodic drawing algorithm for graphs on the torus. Precisely, for any essentially $3$-connected map $G$ on the torus (i.e., $3$-connected in the periodic representation) with $n$ vertices, we can compute in linear time a periodic straight-line drawing of $G$ that is crossing-free and (weakly) convex, on a periodic regular grid $\mathbb{Z}/w\mathbb{Z}\times\mathbb{Z}/h\mathbb{Z}$, with $w\leq 2n$ and $h\leq 1+2n(c+1)$, where $c$ is the face-width of $G$. Since $c\leq\sqrt{2n}$, the grid area is $O(n^{5/2})$.
Document type :
Preprints, Working Papers, ...
Domain :

https://hal.inria.fr/hal-01646724
Contributor : Olivier Devillers <>
Submitted on : Thursday, November 23, 2017 - 4:53:53 PM
Last modification on : Thursday, March 5, 2020 - 6:35:43 PM

### Identifiers

• HAL Id : hal-01646724, version 1
• ARXIV : 1206.1919

### Citation

Luca Castelli Aleardi, Olivier Devillers, Eric Fusy. Canonical ordering for graphs on the cylinder, with applications to periodic straight-line drawings on the flat cylinder and torus. 2017. ⟨hal-01646724⟩

Record views