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

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})$.
Type de document :
Pré-publication, Document de travail
37 pages. 2017
Liste complète des métadonnées

https://hal.inria.fr/hal-01646724
Contributeur : Olivier Devillers <>
Soumis le : jeudi 23 novembre 2017 - 16:53:53
Dernière modification le : jeudi 11 janvier 2018 - 06:28:11

Identifiants

  • 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. 37 pages. 2017. 〈hal-01646724〉

Partager

Métriques

Consultations de la notice

49