2026-04-17T14:24:36Zhttps://recercat.cat/oai/request

oai:recercat.cat:2117/180772026-01-16T06:05:21Zcom_2072_1033col_2072_452950

Universal point subsets for planar graphs Angelini, Patrizio Binucci, Carla Evans, William Hurtado Díaz, Fernando Alfredo Liotta, Giuseppe Mchedlidze, Tamara Meijer, Henk Okamoto, Yoshio Universitat Politècnica de Catalunya. Departament de Matemàtica Aplicada II Universitat Politècnica de Catalunya. DCCG - Grup de recerca en geometria computacional, combinatoria i discreta Àrees temàtiques de la UPC::Matemàtiques i estadística::Geometria::Geometria convexa i discreta Discrete geometry Geometria discreta Classificació AMS::52 Convex and discrete geometry::52C Discrete geometry 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 consider the value F ( n; G ) such that every set of F ( n; G ) points in general position is a universal subset for all graphs with n vertices be- longing to the family G , and we establish upper and lower bounds for F ( n; G ) for different families of planar graphs, including 4-connected planar graphs and nested-triangles graphs. Peer Reviewed Postprint (author’s final draft) 2012 Conference report 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. 978-3-642-35261-4 https://hdl.handle.net/2117/18077 10.1007/978-3-642-35261-4_45 eng http://link.springer.com/chapter/10.1007/978-3-642-35261-4_45 http://creativecommons.org/licenses/by-nc-nd/3.0/es/ Open Access Attribution-NonCommercial-NoDerivs 3.0 Spain 10 p. application/pdf Springer