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 $\ceil{\sqrt{n} \;}$ lower bound on k for the class of planar graphs with n vertices. 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 belonging 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.
Universal Point Subsets for Planar Graphs
BINUCCI, Carla;LIOTTA, Giuseppe;
2012
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 $\ceil{\sqrt{n} \;}$ lower bound on k for the class of planar graphs with n vertices. 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 belonging 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.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.