Loading...
Loading...

Go to the content (press return)

Universal point subsets for planar graphs

Author
Angelini, P.; Binucci, C.; Evans, W.; Hurtado, F.; Liotta, G.; Mchedlidze, T.; Meijer, H.; Okamoto, Y.
Type of activity
Presentation of work at congresses
Name of edition
23rd International Symposium on Algorithms and Computation (ISAAC 2012)
Date of publication
2012
Presentation's date
2012-12-20
Book of congress proceedings
Lecture Notes in Computer Science
First page
423
Last page
432
Publisher
Springer
DOI
https://doi.org/10.1007/978-3-642-35261-4_45 Open in new window
Repository
http://hdl.handle.net/2117/18077 Open in new window
URL
http://link.springer.com/chapter/10.1007/978-3-642-35261-4_45 Open in new window
Abstract
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...
Citation
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.
Group of research
DCG - Discrete and Combinatorial Geometry

Participants

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

Attachments