Local Routing in Planar Orthogonal Subdivisions
Anthony D'Angelo

With the prevalence of mobile devices today and the dawn of the “internet of things”, a lot of research continues to go into being able to route messages efficiently to maximize the usefulness of these low-resourced nodes. Particularly noteworthy is the research done on low-memory local routing algorithms that guarantee delivery.

In these algorithms, the current node holding the message uses only the knowledge of its neighbours' locations as well as some extra information stored in the message header (where the number of available bits is bounded above by some function of the number of nodes) to decide where to forward the packet next, and under these constraints these algorithms guarantee that the message will arrive at its destination in a connected graph. It has been found that guaranteed point-to-point routing can be done in planar convex subdivisions with general positioning using just $1$ bit of extra storage and no predecessor-awareness, and in edge-augmented monotone subdivisions with general positioning using only predecessor-awareness.

I will present an algorithm that can route in planar $x$-monotone orthogonal subdivisions using only $O(1)$ bits of extra memory (using implicit, not explicit predecessor-awareness). I will also present a generalization to $x$-monotone subdivisions with nodes up to “$d$” degree that uses $O(\log d)$ extra bits (where the “$d$” edge-directions are fixed to “$d$” different angles).