Faces in rectilinear drawings of complete graphs

Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F25%3A10504421" target="_blank" >RIV/00216208:11320/25:10504421 - isvavai.cz</a>
Result on the web
<a href="https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=_L4XLnST.x" target="_blank" >https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=_L4XLnST.x</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1016/j.ejc.2025.104217" target="_blank" >10.1016/j.ejc.2025.104217</a>

Result language
angličtina
Original language name
Faces in rectilinear drawings of complete graphs
Original language description
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. (c) 2025 Elsevier Ltd. All rights are reserved, including those for text and data mining, AI training, and similar technologies.
Czech name
—
Czech description
—

Type
J<sub>imp</sub> - Article in a specialist periodical, which is included in the Web of Science database
CEP classification
—
OECD FORD branch
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Project
<a href="/en/project/GX23-04949X" target="_blank" >GX23-04949X: Fundamental questions of discrete geometry</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Publication year
2025
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Similar results(10)