On Point-sets that Support Planar Graphs

Abstract : A universal point-set supports a crossing-free drawing of any planar graph. For a planar graph with $n$ vertices, if bends on edges of the drawing are permitted, universal point-sets of size $n$ are known, but only if the bend-points are in arbitrary positions. If the locations of the bend-points must also be specified as part of the point-set, we prove that any planar graph with $n$ vertices can be drawn on a universal set $\cal S$ of $O(n^2/\log n)$ points with at most one bend per edge and with the vertices and the bend points in $\cal S$. If two bends per edge are allowed, we show that $O(n\log n)$ points are sufficient, and if three bends per edge are allowed, $\Theta(n)$ points are sufficient. When no bends on edges are permitted, no universal point-set of size $o(n^2)$ is known for the class of planar graphs. We show that a set of $n$ points in balanced biconvex position supports the class of maximum degree 3 series-parallel lattices.
Type de document :
Communication dans un congrès
19th International Symposium on Graph Drawing, Sep 2011, Eindhoven, Netherlands. 2011
Liste complète des métadonnées

Littérature citée [10 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00643824
Contributeur : Sylvain Lazard <>
Soumis le : mardi 22 novembre 2011 - 19:39:00
Dernière modification le : jeudi 8 novembre 2018 - 10:58:32
Document(s) archivé(s) le : vendredi 16 novembre 2012 - 11:50:42

Fichier

gdproceedings.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00643824, version 1

Collections

Citation

Vida Dujmović, Will Evans, Sylvain Lazard, William Lenhart, Giuseppe Liotta, et al.. On Point-sets that Support Planar Graphs. 19th International Symposium on Graph Drawing, Sep 2011, Eindhoven, Netherlands. 2011. 〈hal-00643824〉

Partager

Métriques

Consultations de la notice

308

Téléchargements de fichiers

401