Traversal with Enumeration of Geometric Graphs in Bounded Space

DOI10.1142/S0219265919500087MaRDI QIDQ6309509zbMATH OpenWikidataFDO

Authors Sahand Khakabimamaghani, Masood Masjoody, Ladislav Stacho

Publication date 10 November 2018

Full work available at URL https://doi.org/10.1142/S0219265919500087

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85)

Abstract: In this paper, we provide an algorithm for traversing geometric graphs which visits all vertices, and reports every vertex and edge exactly once. To achieve this, we combine a given geometric graph $G$ with the integer lattice, seen as a graph, in such a way that the resulting hypothetical graph can be traversed using the algorithm in cite{Chavez}. To overcome the problem with hypothetical vertices and edges, we develop an algorithm for visiting any $k$th neighborhood of a vertex in a graph straight-line drawn in the plane using $O(logk)$ memory. The memory needed to complete the traversal of a geometric graph then turns out to depend on the maximum ratio of the graph distance and Euclidean distance for pairs of distinct vertices of $G$ at Euclidean distance greater than one and less than $2sqrt2$.

This page was built for publication: Traversal with Enumeration of Geometric Graphs in Bounded Space

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6309509)