Higher-Order Triangular-Distance Delaunay Graphs: Graph-Theoretical Properties

DOI10.1007/978-3-319-14974-5_9zbMath1432.68491arXiv1409.5466OpenAlexW1891529127MaRDI QIDQ5174952

Ahmad Biniaz, Anil Maheshwari, Michiel H. M. Smid

Publication date: 19 February 2015

Published in: Algorithms and Discrete Applied Mathematics (Search for Journal in Brave)

Abstract: We consider an extension of the triangular-distance Delaunay graphs (TD-Delaunay) on a set $P$ of points in the plane. In TD-Delaunay, the convex distance is defined by a fixed-oriented equilateral triangle $riangledown$, and there is an edge between two points in $P$ if and only if there is an empty homothet of $riangledown$ having the two points on its boundary. We consider higher-order triangular-distance Delaunay graphs, namely $k$-TD, which contains an edge between two points if the interior of the homothet of $riangledown$ having the two points on its boundary contains at most $k$ points of $P$. We consider the connectivity, Hamiltonicity and perfect-matching admissibility of $k$-TD. Finally we consider the problem of blocking the edges of $k$-TD.

Full work available at URL: https://arxiv.org/abs/1409.5466

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Related Items (2)

On the Number of Higher Order Delaunay Triangulations ⋮ Some properties of \(k\)-Delaunay and \(k\)-Gabriel graphs

This page was built for publication: Higher-Order Triangular-Distance Delaunay Graphs: Graph-Theoretical Properties