Skip to Main content Skip to Navigation
Journal articles

Dushnik–Miller dimension of TD-Delaunay complexes

Daniel Gonçalves 1 Lucas Isenmann 1
1 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : TD-Delaunay graphs, where TD stands for triangular distance, are a variation of the classical Delaunay triangulations obtained from a specific convex distance function (Chew and Drysdale, 1985). In Bonichon et al. (2010) the authors noticed that every triangulation is the TD-Delaunay graph of a set of points in $\mathbb{R}^2$, and conversely every TD-Delaunay graph is planar. It seems natural to study the generalization of this property in higher dimensions. Such a generalization is obtained by defining an analogue of the triangular distance for $\mathbb{R}^d$. It is easy to see that TD-Delaunay complexes of $\mathbb{R}^{d-1}$ are of Dushnik–Miller dimension $d$. The converse holds for $d=2$ or $3$ and it was conjectured to hold for larger $d$ (Mary, 2010). Here we disprove the conjecture already for $d = 4$.
Document type :
Journal articles
Complete list of metadata
Contributor : Isabelle Gouat <>
Submitted on : Thursday, July 16, 2020 - 3:21:23 PM
Last modification on : Friday, July 17, 2020 - 5:11:29 AM




Daniel Gonçalves, Lucas Isenmann. Dushnik–Miller dimension of TD-Delaunay complexes. European Journal of Combinatorics, Elsevier, 2020, 88, pp.#103110. ⟨10.1016/j.ejc.2020.103110⟩. ⟨lirmm-02900923⟩



Record views