Carregant...
Carregant...

Vés al contingut (premeu Retorn)

Universal point subsets for planar graphs

Autor
Angelini, P.; Binucci, C.; Evans, W.; Hurtado, F.; Liotta, G.; Mchedlidze, T.; Meijer, H.; Okamoto, Y.
Tipus d'activitat
Presentació treball a congrés
Nom de l'edició
23rd International Symposium on Algorithms and Computation (ISAAC 2012)
Any de l'edició
2012
Data de presentació
2012-12-20
Llibre d'actes
Lecture Notes in Computer Science
Pàgina inicial
423
Pàgina final
432
Editor
Springer
DOI
https://doi.org/10.1007/978-3-642-35261-4_45 Obrir en finestra nova
Repositori
http://hdl.handle.net/2117/18077 Obrir en finestra nova
URL
http://link.springer.com/chapter/10.1007/978-3-642-35261-4_45 Obrir en finestra nova
Resum
A set S of k points in the plane is a universal point subset for a class G of planar graphs if every graph belonging to G admits a planar straight-line drawing such that k of its vertices are represented by the points of S . In this paper we study the following main problem: For a given class of graphs, what is the maximum k such that there exists a universal point subset of size k ? We provide a ⌈ √ n ⌉ lower bound on k for the class of planar graphs with n ver- tices. In addition, we con...
Citació
Angelini, P. [et al.]. Universal point subsets for planar graphs. A: International Symposium on Algorithms and Computation. "Lecture Notes in Computer Science". Taipei: Springer, 2012, p. 423-432.
Grup de recerca
DCG - Discrete and Combinatorial Geometry

Participants

  • Angelini, Patrizio  (autor ponent)
  • Binucci, Carla  (autor ponent)
  • Evans, William  (autor ponent)
  • Hurtado Diaz, Fernando Alfredo  (autor ponent)
  • Liotta, Giuseppe  (autor ponent)
  • Mchedlidze, Tamara  (autor ponent)
  • Meijer, Henk  (autor ponent)
  • Okamoto, Yoshio  (autor ponent)

Arxius