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}
}

Search Results

Documents authored by Sollberger, Julia

Counting Triangulations of Fixed Cardinal Degrees (Poster Abstract)

Abstract

Cite as

Thanks for your feedback!

Could not send message