DROPS

Document

Poster Abstract

DOI: 10.4230/LIPIcs.GD.2025.46

Counting Triangulations of Fixed Cardinal Degrees (Poster Abstract)

Authors: Erin Chambers, Tim Ophelders, Anna Schenfisch, and Julia Sollberger

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

Abstract

A fixed set of vertices in the plane may have multiple planar straight-line triangulations in which the degree of each vertex is the same. As such, the degree information does not completely determine the triangulation. We show that even if we know, for each vertex, the number of neighbors in each of the four cardinal directions, the triangulation is not completely determined. We show that counting such triangulations is #P-hard via a reduction from #3-regular bipartite planar vertex cover. pty

Cite as

Erin Chambers, Tim Ophelders, Anna Schenfisch, and Julia Sollberger. Counting Triangulations of Fixed Cardinal Degrees (Poster Abstract). In 33rd International Symposium on Graph Drawing and Network Visualization (GD 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 357, pp. 46:1-46:4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{chambers_et_al:LIPIcs.GD.2025.46,
  author =	{Chambers, Erin and Ophelders, Tim and Schenfisch, Anna and Sollberger, Julia},
  title =	{{Counting Triangulations of Fixed Cardinal Degrees}},
  booktitle =	{33rd International Symposium on Graph Drawing and Network Visualization (GD 2025)},
  pages =	{46:1--46:4},
  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.46},
  URN =		{urn:nbn:de:0030-drops-250325},
  doi =		{10.4230/LIPIcs.GD.2025.46},
  annote =	{Keywords: Planar Triangulations, Degree Information, #P-Hardness}
}

Document

DOI: 10.4230/LIPIcs.SoCG.2025.70

Computing Geomorphologically Salient Networks via Discrete Morse Theory

Authors: Tim Ophelders, Anna Schenfisch, Willem Sonke, and Bettina Speckmann

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

Abstract

Rivers, estuaries, intertidal zones, and other hydrological systems often give rise to complex networks of interconnected channels. Even today, such networks are typically drawn manually by domain experts. Traditional watershed methods for automating this process, where water flows are assumed to follow steepest descent, fail to capture behavior particular to low-relief terrains. At SoCG 2017, Kleinhans et al. proposed a method to construct a network of source-to-sink paths separated by sufficient sediment volume. However, this method is unstable with respect to minor changes of the input terrain, and constructs only channels that flow from one side of the terrain to the other, thereby failing to detect the dead-end channels ("fingers") that characterize intertidal zones. We show how to compute geomorphologically salient networks that avoid these issues. After extending elevation data to a discrete Morse function on the terrain, we identify channels that flow through saddles and have sufficient volume of sediment on both sides. We then detect fingers, which follow the boundary of "spurs" that have sufficient volume of sediment above a particular height. The main challenge here lies in meaningfully modeling salient spurs and determining suitable heights to measure volume. We implemented our method and applied it to real-world data. Our expert users have validated the mathematical modeling by confirming that the resulting (finger) channels indeed constitute a geomorphologically salient network.

Cite as

Tim Ophelders, Anna Schenfisch, Willem Sonke, and Bettina Speckmann. Computing Geomorphologically Salient Networks via Discrete Morse Theory. In 41st International Symposium on Computational Geometry (SoCG 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 332, pp. 70:1-70:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{ophelders_et_al:LIPIcs.SoCG.2025.70,
  author =	{Ophelders, Tim and Schenfisch, Anna and Sonke, Willem and Speckmann, Bettina},
  title =	{{Computing Geomorphologically Salient Networks via Discrete Morse Theory}},
  booktitle =	{41st International Symposium on Computational Geometry (SoCG 2025)},
  pages =	{70:1--70:17},
  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.70},
  URN =		{urn:nbn:de:0030-drops-232221},
  doi =		{10.4230/LIPIcs.SoCG.2025.70},
  annote =	{Keywords: hydrology, network detection, intertidal zones, braided rivers, discrete Morse theory, volume persistence}
}

Search Results

Documents authored by Schenfisch, Anna

Counting Triangulations of Fixed Cardinal Degrees (Poster Abstract)

Abstract

Cite as

Computing Geomorphologically Salient Networks via Discrete Morse Theory

Abstract

Cite as

Thanks for your feedback!

Could not send message