DROPS

Document

DOI: 10.4230/LIPIcs.SoCG.2025.30

Computation of Toroidal Schnyder Woods Made Simple and Fast: From Theory to Practice

Authors: Luca Castelli Aleardi, Eric Fusy, Jyh-Chwen Ko, and Razvan-Stefan Puscasu

Published in: LIPIcs, Volume 332, 41st International Symposium on Computational Geometry (SoCG 2025)

Abstract

We consider the problem of computing Schnyder woods for graphs embedded on the torus. We design simple linear-time algorithms based on canonical orderings that compute toroidal Schnyder woods for simple toroidal triangulations. The Schnyder woods computed by one of our algorithm are crossing and satisfy an additional structural property: at least two of the mono-chromatic components of the Schnyder wood are connected. We also exhibit experimental results empirically confirming three conjectures involving the structure of toroidal and higher genus Schnyder woods.

Cite as

Luca Castelli Aleardi, Eric Fusy, Jyh-Chwen Ko, and Razvan-Stefan Puscasu. Computation of Toroidal Schnyder Woods Made Simple and Fast: From Theory to Practice. In 41st International Symposium on Computational Geometry (SoCG 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 332, pp. 30:1-30:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{castellialeardi_et_al:LIPIcs.SoCG.2025.30,
  author =	{Castelli Aleardi, Luca and Fusy, Eric and Ko, Jyh-Chwen and Puscasu, Razvan-Stefan},
  title =	{{Computation of Toroidal Schnyder Woods Made Simple and Fast: From Theory to Practice}},
  booktitle =	{41st International Symposium on Computational Geometry (SoCG 2025)},
  pages =	{30:1--30:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-370-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{332},
  editor =	{Aichholzer, Oswin and Wang, Haitao},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2025.30},
  URN =		{urn:nbn:de:0030-drops-231825},
  doi =		{10.4230/LIPIcs.SoCG.2025.30},
  annote =	{Keywords: Schnyder woods, toroidal triangulations, canonical ordering}
}

Document

DOI: 10.4230/LIPIcs.SoCG.2024.32

SCARST: Schnyder Compact and Regularity Sensitive Triangulation Data Structure

Authors: Luca Castelli Aleardi and Olivier Devillers

Published in: LIPIcs, Volume 293, 40th International Symposium on Computational Geometry (SoCG 2024)

Abstract

We consider the design of fast and compact representations of the connectivity information of triangle meshes. Although traditional data structures (Half-Edge, Corner Table) are fast and user-friendly, they tend to be memory-expensive. On the other hand, compression schemes, while meeting information-theoretic lower bounds, do not support navigation within the mesh structure. Compact representations provide an advantageous balance for representing large meshes, enabling a judicious compromise between memory consumption and fast implementation of navigational operations. We propose new representations that are sensitive to the regularity of the graph while still having worst case guarantees. For all our data structures we have both an interesting storage cost, typically 2 or 3 r.p.v. (references per vertex) in the case of very regular triangulations, and provable upper bounds in the worst case scenario. One of our solutions has a worst case cost of 3.33 r.p.v., which is currently the best-known bound improving the previous 4 r.p.v. [Castelli et al. 2018]. Our representations have slightly slower running times (factors 1.5 to 4) than classical data structures. In our experiments we compare on various meshes runtime and memory performance of our representations with those of the most efficient existing solutions.

Cite as

Luca Castelli Aleardi and Olivier Devillers. SCARST: Schnyder Compact and Regularity Sensitive Triangulation Data Structure. In 40th International Symposium on Computational Geometry (SoCG 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 293, pp. 32:1-32:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{castellialeardi_et_al:LIPIcs.SoCG.2024.32,
  author =	{Castelli Aleardi, Luca and Devillers, Olivier},
  title =	{{SCARST: Schnyder Compact and Regularity Sensitive Triangulation Data Structure}},
  booktitle =	{40th International Symposium on Computational Geometry (SoCG 2024)},
  pages =	{32:1--32:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-316-4},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{293},
  editor =	{Mulzer, Wolfgang and Phillips, Jeff M.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2024.32},
  URN =		{urn:nbn:de:0030-drops-199779},
  doi =		{10.4230/LIPIcs.SoCG.2024.32},
  annote =	{Keywords: Meshes, compression, triangulations, compact representations}
}

Search Results

Documents authored by Castelli Aleardi, Luca

Computation of Toroidal Schnyder Woods Made Simple and Fast: From Theory to Practice

Abstract

Cite as

SCARST: Schnyder Compact and Regularity Sensitive Triangulation Data Structure

Abstract

Cite as

Thanks for your feedback!

Could not send message