3532 articles – 5253 Notices  [english version]

inria-00431769, version 1

Universal Sets of n Points for One-bend Drawings of Planar Graphs with n Vertices

Hazel Everett () 1, Sylvain Lazard () 1, Giuseppe Liotta 2, Steve Wismath a, 3

Journal of Discrete and Computational Geometry 43, 2 (2010) 272-288

Résumé : This paper shows that any planar graph with $n$ vertices can be point-set embedded with at most one bend per edge on a universal set of n points in the plane. An implication of this result is that any number of planar graphs admit a simultaneous embedding without mapping with at most one bend per edge.

  • a –  UNIVERSITY OF LETHBRIDGE
  • 1 :  VEGAS (INRIA Lorraine - LORIA)
  • INRIA – CNRS : UMR7503 – Université Henri Poincaré - Nancy I – Université Nancy II – Institut National Polytechnique de Lorraine (INPL)
  • 2 :  School of Computing
  • University of Perugia
  • 3 :  Department of Mathematics and Computer Science
  • University of Lethbridge
  • Domaine : Informatique/Géométrie algorithmique
 
  • inria-00431769, version 1
  • http://hal.inria.fr/inria-00431769
  • oai:hal.inria.fr:inria-00431769
  • Contributeur : Sylvain Lazard <>
  • Soumis le : Vendredi 13 Novembre 2009, 09:41:24
  • Dernière modification le : Mercredi 3 Mars 2010, 14:21:37