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.
Copyright is held by the author.
The author granted permission for the file to be printed and for the text to be copied and pasted.
Supervisor or Senior Supervisor
Thesis advisor: Stacho, Ladislav
Member of collection