DROPS

Document

DOI: 10.4230/LIPIcs.GD.2025.25

Characterizing and Recognizing Twistedness

Authors: Oswin Aichholzer, Alfredo García, Javier Tejel, Birgit Vogtenhuber, and Alexandra Weinberger

Published in: LIPIcs, Volume 357, 33rd International Symposium on Graph Drawing and Network Visualization (GD 2025)

Abstract

In a simple drawing of a graph, any two edges intersect in at most one point (either a common endpoint or a proper crossing). A simple drawing is generalized twisted if it fulfills certain rather specific constraints on how the edges are drawn. An abstract rotation system of a graph assigns to each vertex a cyclic order of its incident edges. A realizable rotation system is one that admits a simple drawing such that at each vertex, the edges emanate in that cyclic order, and a generalized twisted rotation system can be realized as a generalized twisted drawing. Generalized twisted drawings have initially been introduced to obtain improved bounds on the size of plane substructures in any simple drawing of K_n. They have since gained independent interest due to their surprising properties. However, the definition of generalized twisted drawings is very geometric and drawing-specific. In this paper, we develop characterizations of generalized twisted drawings that enable a purely combinatorial view on these drawings and lead to efficient recognition algorithms. Concretely, we show that for any n ≥ 7, an abstract rotation system of K_n is generalized twisted if and only if all subrotation systems induced by five vertices are generalized twisted. This implies a drawing-independent and concise characterization of generalized twistedness. Besides, the result yields a simple O(n⁵)-time algorithm to decide whether an abstract rotation system is generalized twisted and sheds new light on the structural features of simple drawings. We further develop a characterization via the rotations of a pair of vertices in a drawing, which we then use to derive an O(n²)-time algorithm to decide whether a realizable rotation system is generalized twisted.

Cite as

Oswin Aichholzer, Alfredo García, Javier Tejel, Birgit Vogtenhuber, and Alexandra Weinberger. Characterizing and Recognizing Twistedness. In 33rd International Symposium on Graph Drawing and Network Visualization (GD 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 357, pp. 25:1-25:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{aichholzer_et_al:LIPIcs.GD.2025.25,
  author =	{Aichholzer, Oswin and Garc{\'\i}a, Alfredo and Tejel, Javier and Vogtenhuber, Birgit and Weinberger, Alexandra},
  title =	{{Characterizing and Recognizing Twistedness}},
  booktitle =	{33rd International Symposium on Graph Drawing and Network Visualization (GD 2025)},
  pages =	{25:1--25:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-403-1},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{357},
  editor =	{Dujmovi\'{c}, Vida and Montecchiani, Fabrizio},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.GD.2025.25},
  URN =		{urn:nbn:de:0030-drops-250116},
  doi =		{10.4230/LIPIcs.GD.2025.25},
  annote =	{Keywords: generalized twisted drawings, simple drawings, rotation systems, recognition, combinatorial characterization, efficient algorithms}
}

Document

DOI: 10.4230/LIPIcs.SoCG.2022.5

Twisted Ways to Find Plane Structures in Simple Drawings of Complete Graphs

Authors: Oswin Aichholzer, Alfredo García, Javier Tejel, Birgit Vogtenhuber, and Alexandra Weinberger

Published in: LIPIcs, Volume 224, 38th International Symposium on Computational Geometry (SoCG 2022)

Abstract

Simple drawings are drawings of graphs in which the edges are Jordan arcs and each pair of edges share at most one point (a proper crossing or a common endpoint). We introduce a special kind of simple drawings that we call generalized twisted drawings. A simple drawing is 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. Via this new class of simple drawings, we show that every simple drawing of the complete graph with n vertices contains Ω(n^{1/2}) pairwise disjoint edges and a plane path of length Ω((log n)/(log log n)). Both results improve over previously known best lower bounds. On the way we show several structural results about and properties of generalized twisted drawings. We further present different characterizations of generalized twisted drawings, which might be of independent interest.

Cite as

Oswin Aichholzer, Alfredo García, Javier Tejel, Birgit Vogtenhuber, and Alexandra Weinberger. Twisted Ways to Find Plane Structures in Simple Drawings of Complete Graphs. In 38th International Symposium on Computational Geometry (SoCG 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 224, pp. 5:1-5:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{aichholzer_et_al:LIPIcs.SoCG.2022.5,
  author =	{Aichholzer, Oswin and Garc{\'\i}a, Alfredo and Tejel, Javier and Vogtenhuber, Birgit and Weinberger, Alexandra},
  title =	{{Twisted Ways to Find Plane Structures in Simple Drawings of Complete Graphs}},
  booktitle =	{38th International Symposium on Computational Geometry (SoCG 2022)},
  pages =	{5:1--5:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-227-3},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{224},
  editor =	{Goaoc, Xavier and Kerber, Michael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2022.5},
  URN =		{urn:nbn:de:0030-drops-160136},
  doi =		{10.4230/LIPIcs.SoCG.2022.5},
  annote =	{Keywords: Simple drawings, simple topological graphs, disjoint edges, plane matching, plane path}
}

Search Results

Documents authored by Tejel, Javier

Characterizing and Recognizing Twistedness

Abstract

Cite as

Twisted Ways to Find Plane Structures in Simple Drawings of Complete Graphs

Abstract

Cite as

Thanks for your feedback!

Could not send message