425 articles – 193 Notices  [english version]

hal-00684510, version 1

## On Point-sets that Support Planar Graphs

Vida Dujmovic a1, Will Evans 2, Sylvain Lazard (, ) 3, William Lenhart b4, Giuseppe Liotta c5, David Rappaport 6, Steve Wismath d7

Computational Geometry 43, 1 (2013) 29--50

Résumé : 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, $O(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.

• a –  Carleton University
• b –  Williams College
• c –  Universita degli Studi di Perugua
• d –  UNIVERSITY OF LETHBRIDGE
• 1 :  School of computer science [Ottawa] (SCS)
• Carleton University
• 2 :  Computer Science Department (UBC-Computer Science)
• University of British Columbia
• 3 :  VEGAS (INRIA Nancy - Grand Est / LORIA)
• INRIA – CNRS : UMR7503 – Université de Lorraine
• 4 :  Computer Science Department [Williamstown MA]
• Williams College
• 5 :  School of Computing
• University of Perugia
• 6 :  Department of Electrical and Computer Engineering [Queen's University Kingston]
• Queen's University
• 7 :  Department of Mathematics and Computer Science
• University of Lethbridge
• Domaine : Informatique/Géométrie algorithmique

• hal-00684510, version 1
• oai:hal.inria.fr:hal-00684510
• Contributeur :
• Soumis le : Lundi 2 Avril 2012, 12:17:43
• Dernière modification le : Vendredi 26 Octobre 2012, 15:20:09