Počet záznamů: 1
Hamiltonicity for Convex Shape Delaunay and Gabriel Graphs
- 1.
SYSNO ASEP 0523630 Druh ASEP J - Článek v odborném periodiku Zařazení RIV J - Článek v odborném periodiku Poddruh J Článek ve WOS Název Hamiltonicity for Convex Shape Delaunay and Gabriel Graphs Tvůrce(i) Bose, P. (CA)
Cano, P. (CA)
Saumell, Maria (UIVT-O) RID, SAI, ORCID
Silveira, R.I. (ES)Číslo článku 101629 Zdroj.dok. Computational Geometry-Theory and Applications. - : Elsevier - ISSN 0925-7721
Roč. 89, August 2020 (2020)Poč.str. 17 s. Forma vydání Online - E Jazyk dok. eng - angličtina Země vyd. NL - Nizozemsko Klíč. slova Delaunay graphs ; Hamiltonicity ; Gabriel graphs Vědní obor RIV BA - Obecná matematika Obor OECD Pure mathematics CEP GJ19-06792Y GA ČR - Grantová agentura ČR Způsob publikování Omezený přístup Institucionální podpora UIVT-O - RVO:67985807 UT WOS 000532684200006 EID SCOPUS 85081686829 DOI 10.1016/j.comgeo.2020.101629 Anotace We study Hamiltonicity for some of the most general variants of Delaunay and Gabriel graphs. Instead of defining these proximity graphs using circles, we use an arbitrary convex shape C. Let S be a point set in the plane. The k-order Delaunay graph of S, denoted k-DGC(S), has vertex set S, and edges defined as follows. Given p,q∈S, pq is an edge of k-DGC(S) provided there exists some homothet of C with p and q on its boundary and containing at most k points of S different from p and q. The k-order Gabriel graph, denoted k-GGC(S), is defined analogously, except that the homothets considered are restricted to be smallest homothets of C with p and q on the boundary. We provide upper bounds on the minimum value of k for which k-GGC(S) is Hamiltonian. Since k-GGC(S) ⊆ k-DGC(S), all results carry over to k-DGC(S). In particular, we give upper bounds of 24 for every C and 15 for every point-symmetric C. We also improve these bounds to 7 for squares, 11 for regular hexagons, 12 for regular octagons, and 11 for even-sided regular t-gons (for t≥10). These constitute the first general results on Hamiltonicity for convex shape Delaunay and Gabriel graphs. In addition, we show lower bounds of k=3 and k=6 on the existence of a bottleneck Hamiltonian cycle in the k-order Gabriel graph for squares and hexagons, respectively. Finally, we construct a point set such that for an infinite family of regular polygons Pt, the Delaunay graph DGPt does not contain a Hamiltonian cycle. Pracoviště Ústav informatiky Kontakt Tereza Šírová, sirova@cs.cas.cz, Tel.: 266 053 800 Rok sběru 2021 Elektronická adresa http://dx.doi.org/10.1016/j.comgeo.2020.101629
Počet záznamů: 1