Counting Triangulations of Fixed Cardinal Degrees

Erin Chambers; Tim Ophelders; Anna Schenfisch; Julia Sollberger

doi:10.4230/LIPIcs.GD.2025.46

Counting Triangulations of Fixed Cardinal Degrees

Erin Chambers^*
, Tim Ophelders^*
, Anna Schenfisch^*
, Julia Sollberger^*

^*Corresponding author for this work

Sub Geometric Computing

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

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.

Original language	English
Title of host publication	33rd International Symposium on Graph Drawing and Network Visualization, GD 2025
Editors	Vida Dujmovic, Fabrizio Montecchiani
Publisher	Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)	9783959774031
DOIs	https://doi.org/10.4230/LIPIcs.GD.2025.46
Publication status	Published - 2025
Event	33rd International Symposium on Graph Drawing and Network Visualization, GD 2025 - Norrkoping, Sweden Duration: 24 Sept 2025 → 26 Sept 2025

Publication series

Name	Leibniz International Proceedings in Informatics, LIPIcs
Volume	357
ISSN (Print)	1868-8969

Conference

Conference	33rd International Symposium on Graph Drawing and Network Visualization, GD 2025
Country/Territory	Sweden
City	Norrkoping
Period	24/09/25 → 26/09/25

Bibliographical note

Publisher Copyright:
© Erin Chambers, Tim Ophelders, Anna Schenfisch, and Julia Sollberger; licensed under Creative Commons License CC-BY 4.0.

Keywords

#P-Hardness
Degree Information
Planar Triangulations

Access to Document

10.4230/LIPIcs.GD.2025.46Licence: CC BY

LIPIcs.GD.2025.46Final published version, 710 KBLicence: CC BY

Cite this

Chambers, E., Ophelders, T., Schenfisch, A., & Sollberger, J. (2025). Counting Triangulations of Fixed Cardinal Degrees. In V. Dujmovic, & F. Montecchiani (Eds.), 33rd International Symposium on Graph Drawing and Network Visualization, GD 2025 Article 46 (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 357). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. https://doi.org/10.4230/LIPIcs.GD.2025.46

Chambers, Erin ; Ophelders, Tim ; Schenfisch, Anna et al. / Counting Triangulations of Fixed Cardinal Degrees. 33rd International Symposium on Graph Drawing and Network Visualization, GD 2025. editor / Vida Dujmovic ; Fabrizio Montecchiani. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2025. (Leibniz International Proceedings in Informatics, LIPIcs).

@inproceedings{a49d54e3e18046ad803c7332bfc796bc,

title = "Counting Triangulations of Fixed Cardinal Degrees",

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.",

keywords = "\#P-Hardness, Degree Information, Planar Triangulations",

author = "Erin Chambers and Tim Ophelders and Anna Schenfisch and Julia Sollberger",

note = "Publisher Copyright: {\textcopyright} Erin Chambers, Tim Ophelders, Anna Schenfisch, and Julia Sollberger; licensed under Creative Commons License CC-BY 4.0.; 33rd International Symposium on Graph Drawing and Network Visualization, GD 2025 ; Conference date: 24-09-2025 Through 26-09-2025",

year = "2025",

doi = "10.4230/LIPIcs.GD.2025.46",

language = "English",

series = "Leibniz International Proceedings in Informatics, LIPIcs",

publisher = "Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing",

editor = "Vida Dujmovic and Fabrizio Montecchiani",

booktitle = "33rd International Symposium on Graph Drawing and Network Visualization, GD 2025",

address = "Germany",

}

Chambers, E, Ophelders, T, Schenfisch, A & Sollberger, J 2025, Counting Triangulations of Fixed Cardinal Degrees. in V Dujmovic & F Montecchiani (eds), 33rd International Symposium on Graph Drawing and Network Visualization, GD 2025., 46, Leibniz International Proceedings in Informatics, LIPIcs, vol. 357, Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 33rd International Symposium on Graph Drawing and Network Visualization, GD 2025, Norrkoping, Sweden, 24/09/25. https://doi.org/10.4230/LIPIcs.GD.2025.46

Counting Triangulations of Fixed Cardinal Degrees. / Chambers, Erin; Ophelders, Tim; Schenfisch, Anna et al.
33rd International Symposium on Graph Drawing and Network Visualization, GD 2025. ed. / Vida Dujmovic; Fabrizio Montecchiani. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2025. 46 (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 357).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - Counting Triangulations of Fixed Cardinal Degrees

AU - Chambers, Erin

AU - Ophelders, Tim

AU - Schenfisch, Anna

AU - Sollberger, Julia

N1 - Publisher Copyright: © Erin Chambers, Tim Ophelders, Anna Schenfisch, and Julia Sollberger; licensed under Creative Commons License CC-BY 4.0.

PY - 2025

Y1 - 2025

N2 - 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.

AB - 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.

KW - #P-Hardness

KW - Degree Information

KW - Planar Triangulations

UR - https://www.scopus.com/pages/publications/105031455205

U2 - 10.4230/LIPIcs.GD.2025.46

DO - 10.4230/LIPIcs.GD.2025.46

M3 - Conference contribution

AN - SCOPUS:105031455205

T3 - Leibniz International Proceedings in Informatics, LIPIcs

BT - 33rd International Symposium on Graph Drawing and Network Visualization, GD 2025

A2 - Dujmovic, Vida

A2 - Montecchiani, Fabrizio

PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing

T2 - 33rd International Symposium on Graph Drawing and Network Visualization, GD 2025

Y2 - 24 September 2025 through 26 September 2025

ER -

Chambers E, Ophelders T, Schenfisch A, Sollberger J. Counting Triangulations of Fixed Cardinal Degrees. In Dujmovic V, Montecchiani F, editors, 33rd International Symposium on Graph Drawing and Network Visualization, GD 2025. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. 2025. 46. (Leibniz International Proceedings in Informatics, LIPIcs). doi: 10.4230/LIPIcs.GD.2025.46

Counting Triangulations of Fixed Cardinal Degrees

Abstract

Publication series

Conference

Bibliographical note

Keywords

Access to Document

Other files and links

Fingerprint

Cite this