2026-07-24T05:17:04Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:25032 2026-02-09T07:53:54Z ddc:004 open_access

Counting Triangulations of Fixed Cardinal Degrees (Poster Abstract) Chambers, Erin Ophelders, Tim Schenfisch, Anna Sollberger, Julia Planar Triangulations Degree Information #P-Hardness 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 Schloss Dagstuhl – Leibniz-Zentrum für Informatik Erin Chambers and Tim Ophelders and Anna Schenfisch and Julia Sollberger 2025 Is Part Of LIPIcs, Volume 357, 33rd International Symposium on Graph Drawing and Network Visualization (GD 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.GD.2025.46 urn:nbn:de:0030-drops-250325 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.GD.2025.46 eng https://creativecommons.org/licenses/by/4.0/legalcode