Malmö University Publications
System disruptions
There are recurring service disruptions on some of the search portals due to high traffic. We are working to resolve the issue, you may temporarily encounter an error message.
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Faces in rectilinear drawings of complete graphs
Department of Applied Mathematics, Faculty of Mathematics and Physics, Charles University, Czech Republic.
Malmö University, Faculty of Technology and Society (TS), Department of Computer Science and Media Technology (DVMT). Malmö University, Sustainable Digitalisation Research Centre (SDRC).ORCID iD: 0000-0002-2161-6571
Departament de Matemàtiques Universitat Politècnica de Catalunya, Barcelona, Spain.
Computer Science Institute, Faculty of Mathematics and Physics, Charles University, Czech Republic.
2025 (English)In: European journal of combinatorics (Print), ISSN 0195-6698, E-ISSN 1095-9971, Vol. 130, article id 104217Article in journal (Refereed) Published
Abstract [en]

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.

Place, publisher, year, edition, pages
Elsevier, 2025. Vol. 130, article id 104217
National Category
Computer Sciences
Identifiers
URN: urn:nbn:se:mau:diva-78800DOI: 10.1016/j.ejc.2025.104217ISI: 001537526400001Scopus ID: 2-s2.0-105010008046OAI: oai:DiVA.org:mau-78800DiVA, id: diva2:1988200
Funder
Swedish Research CouncilSwedish Research CouncilAvailable from: 2025-08-11 Created: 2025-08-11 Last updated: 2026-03-10Bibliographically approved

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full textScopus

Authority records

Brötzner, Anna

Search in DiVA

By author/editor
Brötzner, Anna
By organisation
Department of Computer Science and Media Technology (DVMT)Sustainable Digitalisation Research Centre (SDRC)
In the same journal
European journal of combinatorics (Print)
Computer Sciences

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 138 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf