Empty Triangles in Generalized Twisted Drawings of Kn

Alfredo García, Javier Tejel, Birgit Vogtenhuber, Alexandra Weinberger*

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference paperpeer-review

Abstract

Simple drawings are drawings of graphs in the plane or on the sphere such that vertices are distinct points, edges are Jordan arcs connecting their endpoints, and edges intersect at most once (either in a proper crossing or in a shared endpoint). Simple drawings are generalized twisted if there is a point O such that every ray emanating from O crosses every edge of the drawing at most once and there is a ray emanating from O which crosses every edge exactly once. We show that all generalized twisted drawings of Kn contain exactly 2 n- 4 empty triangles, by this making a substantial step towards proving the conjecture that this is the case for every simple drawing of Kn.

Original languageEnglish
Title of host publicationGraph Drawing and Network Visualization - 30th International Symposium, GD 2022, Revised Selected Papers
EditorsPatrizio Angelini, Reinhard von Hanxleden
PublisherSpringer Science and Business Media Deutschland GmbH
Pages40-48
Number of pages9
ISBN (Print)9783031222023
DOIs
Publication statusPublished - 2023
Event30th International Symposium on Graph Drawing and Network Visualization: GD 2022 - Tokyo, Japan
Duration: 13 Sept 202216 Jan 2023

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume13764 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference30th International Symposium on Graph Drawing and Network Visualization
Abbreviated titleGD 2022
Country/TerritoryJapan
CityTokyo
Period13/09/2216/01/23

Keywords

  • Empty triangles
  • Simple drawings
  • Simple topological graphs

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science

Fingerprint

Dive into the research topics of 'Empty Triangles in Generalized Twisted Drawings of Kn'. Together they form a unique fingerprint.

Cite this