2025/06/30 by Martin Balko, Anna Brötzner, Balko, Martin +5
Computer Science · Mathematics · #Combinatorics (math.CO) #Digital Image Processing Techniques #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Limits and Structures in Graph Theory #Point processes and geometric inequalities
paper · pdf · doi:10.48550/arxiv.2507.00313
openalex publication_date 2025/06/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We initiate the study of extremal problems about faces in convex rectilinear drawings of~Kn, that is, drawings where vertices are represented by points in the plane in convex position and edges by line segments between the points representing the end-vertices. We show that if a convex rectilinear drawing of Kn does not contain a common interior point of at least three edges, then there is always a face forming a convex 5-gon while there are such drawings without any face forming a convex k-gon with k ≥ 6. A convex rectilinear drawing of Kn is regular if its vertices correspond to vertices of a regular convex n-gon. We characterize positive integers n for which regular drawings of Kn contain a face forming a convex 5-gon. To our knowledge, this type of problems has not been considered in the literature before and so we also pose several new natural open problems.