Faces in rectilinear drawings of complete graphs
Abstrak
We initiate the study of extremal problems about faces in convex rectilinear drawings of~$K_n$, 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 $K_n$ 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 \geq 6$. A convex rectilinear drawing of $K_n$ is \emph{regular} if its vertices correspond to vertices of a regular convex $n$-gon. We characterize positive integers $n$ for which regular drawings of $K_n$ 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.
Penulis (4)
Martin Balko
Anna Brötzner
Fabian Klute
Josef Tkadlec
Akses Cepat
- Tahun Terbit
- 2025
- Bahasa
- en
- Sumber Database
- arXiv
- Akses
- Open Access ✓