Canonical ordering for graphs on the cylinder, with applications to periodic straight-line drawings on the flat cylinder and torus - Archive ouverte HAL Access content directly
Preprints, Working Papers, ... Year :

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

(1) , (2) , (1)
1
2
Olivier Devillers
Eric Fusy
• Function : Author
• PersonId : 839860

#### 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})$.

### Dates and versions

hal-01646724 , version 1 (23-11-2017)

### Identifiers

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

### Cite

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⟩

### Export

BibTeX TEI Dublin Core DC Terms EndNote Datacite

489 View