2017/08/30 by Paul Manuel, Manuel, Paul, Sandi Klavžar +1 · 1 citation
Computer Science · #05C12 #05C70 #68Q25 #Advanced Graph Theory Research #Combinatorics (math.CO) #Computational Geometry and Mesh Generation #Constraint Satisfaction and Optimization #FOS: Mathematics
paper · pdf · doi:10.48550/arxiv.1708.09130
openalex publication_date 2017/08/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The classical no-three-in-line problem is to find the maximum number of points that can be placed in the n × n grid so that no three points lie on a line. Given a set S of points in an Euclidean plane, the General Position Subset Selection Problem is to find a maximum subset S' of S such that no three points of S' are collinear. Motivated by these problems, the following graph theory variation is introduced: Given a graph G, determine a largest set S of vertices of G such that no three vertices of S lie on a common geodesic. Such a set is a gp-set of G and its size is the gp-number \rm gp(G) of G. Upper bounds on \rm gp(G) in terms of different isometric covers are given and used to determine the gp-number of several classes of graphs. Connections between general position sets and packings are investigated and used to give lower bounds on the gp-number. It is also proved that the general position problem is NP-complete.