Home > Research > Publications & Outputs > Determining triangulations and quadrangulations...

Research

Associated organisational unit

Electronic data

  • triangulation-reconstruction-v2

    Accepted author manuscript, 297 KB, PDF document

    Available under license: CC BY: Creative Commons Attribution 4.0 International License

Links

Text available via DOI:

Keywords

View graph of relations

Determining triangulations and quadrangulations by boundary distances

Research output: Contribution to Journal/Magazine › Journal article › peer-review

Published

Standard

Determining triangulations and quadrangulations by boundary distances. / Haslegrave, John.
In: Journal of Combinatorial Theory, Series B, Vol. 163, 30.11.2023, p. 233-255.

Research output: Contribution to Journal/Magazine › Journal article › peer-review

Harvard

Haslegrave, J 2023, 'Determining triangulations and quadrangulations by boundary distances', Journal of Combinatorial Theory, Series B, vol. 163, pp. 233-255. https://doi.org/10.1016/j.jctb.2023.08.002

APA

Haslegrave, J. (2023). Determining triangulations and quadrangulations by boundary distances. Journal of Combinatorial Theory, Series B, 163, 233-255. https://doi.org/10.1016/j.jctb.2023.08.002

Vancouver

Haslegrave J. Determining triangulations and quadrangulations by boundary distances. Journal of Combinatorial Theory, Series B. 2023 Nov 30;163:233-255. Epub 2023 Aug 31. doi: 10.1016/j.jctb.2023.08.002

Author

Haslegrave, John. / Determining triangulations and quadrangulations by boundary distances. In: Journal of Combinatorial Theory, Series B. 2023 ; Vol. 163. pp. 233-255.

Bibtex

@article{40423689a9ed4d53bebe5a777203aeca,
title = "Determining triangulations and quadrangulations by boundary distances",
abstract = "We show that if all internal vertices of a disc triangulation have degree at least 6, then the full structure can be determined from the pairwise graph distances between boundary vertices. A similar result holds for disc quadrangulations with all internal vertices having degree at least 4. This confirms a conjecture of Itai Benjamini. Both degree bounds are best possible, and correspond to local non-positive curvature. However, we show that a natural conjecture for a “mixed” version of the two results is not true.",
keywords = "Planar graph, Triangulation, Graph distance, Boundary rigidity, Graph reconstruction",
author = "John Haslegrave",
year = "2023",
month = nov,
day = "30",
doi = "10.1016/j.jctb.2023.08.002",
language = "English",
volume = "163",
pages = "233--255",
journal = "Journal of Combinatorial Theory, Series B",
issn = "0095-8956",
publisher = "Academic Press Inc.",

}

RIS

TY - JOUR

T1 - Determining triangulations and quadrangulations by boundary distances

AU - Haslegrave, John

PY - 2023/11/30

Y1 - 2023/11/30

N2 - We show that if all internal vertices of a disc triangulation have degree at least 6, then the full structure can be determined from the pairwise graph distances between boundary vertices. A similar result holds for disc quadrangulations with all internal vertices having degree at least 4. This confirms a conjecture of Itai Benjamini. Both degree bounds are best possible, and correspond to local non-positive curvature. However, we show that a natural conjecture for a “mixed” version of the two results is not true.

AB - We show that if all internal vertices of a disc triangulation have degree at least 6, then the full structure can be determined from the pairwise graph distances between boundary vertices. A similar result holds for disc quadrangulations with all internal vertices having degree at least 4. This confirms a conjecture of Itai Benjamini. Both degree bounds are best possible, and correspond to local non-positive curvature. However, we show that a natural conjecture for a “mixed” version of the two results is not true.

KW - Planar graph

KW - Triangulation

KW - Graph distance

KW - Boundary rigidity

KW - Graph reconstruction

U2 - 10.1016/j.jctb.2023.08.002

DO - 10.1016/j.jctb.2023.08.002

M3 - Journal article

VL - 163

SP - 233

EP - 255

JO - Journal of Combinatorial Theory, Series B

JF - Journal of Combinatorial Theory, Series B

SN - 0095-8956

ER -