Higher-order triangular-distance Delaunay graphs: graph-theoretical properties

DOI10.1016/j.comgeo.2015.07.003zbMath1329.05175OpenAlexW2757769355MaRDI QIDQ904106

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

Publication date: 15 January 2016

Published in: Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.comgeo.2015.07.003

zbMATH Keywords

matchingHamiltonian cycleDelaunay graphtriangular distance

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Distance in graphs (05C12) Connectivity (05C40) Eulerian and Hamiltonian graphs (05C45)

Related Items

Strong matching of points with geometric shapes, Computational complexity of the vertex cover problem in the class of planar triangulations, Hamiltonicity for convex shape Delaunay and Gabriel graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Witness Gabriel graphs
• Some properties of \(k\)-Delaunay and \(k\)-Gabriel graphs
• Blocking Delaunay triangulations
• Fixed-orientation equilateral triangle matching of point sets
• Toughness and Delaunay triangulations
• A non-Hamiltonian, nondegenerate Delaunay triangulation
• Solving the Euclidean bottleneck matching problem by \(k\)-relative neighborhood graphs
• Solving the Euclidean bottleneck biconnected edge subgraph problem by 2- relative neighborhood graphs
• There are planar graphs almost as good as the complete graph
• 10-Gabriel graphs are Hamiltonian
• On the stretch factor of convex Delaunay graphs
• Connections between Theta-Graphs, Delaunay Triangulations, and Orthogonal Surfaces
• ON STRUCTURAL AND GRAPH THEORETIC PROPERTIES OF HIGHER ORDER DELAUNAY GRAPHS
• Algorithms for two bottleneck optimization problems
• 20‐relative neighborhood graphs are hamiltonian
• The Factorization of Linear Graphs