Faces in rectilinear drawings of complete graphs
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866908428807438336 |
|---|---|
| author | Balko, Martin Brötzner, Anna Klute, Fabian Tkadlec, Josef |
| author_facet | Balko, Martin Brötzner, Anna Klute, Fabian Tkadlec, Josef |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2507_00313 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Faces in rectilinear drawings of complete graphs Balko, Martin Brötzner, Anna Klute, Fabian Tkadlec, Josef Combinatorics Discrete Mathematics 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. |
| title | Faces in rectilinear drawings of complete graphs |
| topic | Combinatorics Discrete Mathematics |
| url | https://arxiv.org/abs/2507.00313 |