LOW MEMORY GRAPH TRAVERSAL
Samson Kenneth Ray Bassett · Summit (Simon Fraser University) · 2010
We provide two traversal algorithms. First, we demonstrate that there exists a local orientation for any anonymous graph G, provided that G is not a star graph, and G does not have any induced subgraph that is isomorphic to a path on four vertices. We show that it is possible to periodically traverse G with period at most 2n - 2; this matches the lower bound for the period for general graphs. Next, we provide a traversal for labelled graphs given that they satisfy two properties, which we define. The properties that we define and use are inspired by the properties of geometric planar graphs.