On the Spanning and Routing Properties of Grade-1 Emanation Graphs

Abstract

Families of geometric spanners are sets of graphs G = (V, E) defined by construction rules such that for any two vertices p, q ∈ V , there exists a path whose length is at most σ|pq|, where σ is a constant. In this work, we study a family of graphs called grade-1 emanation graphs, obtained by taking a point set P , shooting rays from each point in four equidistant directions, introducing Steiner vertices at ray intersections, and interrupting rays upon intersection. We first show that grade 1 emanation graphs form a subclass of motorcycle graphs. We then investigate their spanning properties. In particular, we strengthen existing results by showing that grade-1 emanation graphs are √10-spanners even when one of the vertices is a Steiner vertex, while no constant stretch factor exists when both vertices are Steiner vertices. We next study local routing on grade-1 emanation graphs. We demonstrate that several classical routing strategies, including greedy, compass, and greedy-compass routing, all fail in this setting, and that face routing can incur arbitrarily large routing ratios. To address this, we introduce a new routing algorithm, the Marking Algorithm, and show that it guarantees delivery on grade-1 emanation graphs in general position. Our analysis further establishes a routing ratio of 2+24√2 for all paths that do not contain a subpath belonging to a group of subpaths, which we identify as pattern G10. These results provide new insight into the structure and limitations of emanation graphs and contribute to the broader understanding of geometric spanners and local routing algorithms.