### Abstract

We show that it is possible to route locally and com-petitively on two bounded-degree plane 6-spanners, one with maximum degree 12 and the other with maximum degree 9. Both spanners are subgraphs of the empty equilateral triangle Delaunay triangulation. First, in a weak routing model where the only information stored at each vertex is its neighbourhood, we show how to find a path between any two vertices of a 6-spanner of max-imum degree 12, such that the path has length at most 95/ √ 3 times the straight-line distance between the ver-tices. In a slightly stronger model, where in addition to the neighbourhood of each vertex, we store O(1) addi-tional information, we show how to find a path that has length at most 15/ √ 3 times the Euclidean distance both in a 6-spanner of maximum degree 12 and a 6-spanner of maximum degree 9.

Original language | English |
---|---|

Title of host publication | Proceedings of the 24th Canadian Conference on Computational Geometry |

Publication date | 2012 |

Pages | 285-290 |

Publication status | Published - 2012 |

Event | The 24th Canadian Conference on Computational Geometry - Charlottetown, Canada Duration: 8. Aug 2012 → 10. Aug 2012 Conference number: 24 |

### Conference

Conference | The 24th Canadian Conference on Computational Geometry |
---|---|

Number | 24 |

Country | Canada |

City | Charlottetown |

Period | 08/08/2012 → 10/08/2012 |

## Fingerprint Dive into the research topics of 'Competitive Routing on a Bounded-Degree Plane Spanner'. Together they form a unique fingerprint.

## Cite this

Bose, P., Fagerberg, R., Renssen, A. V., & Verdonschot, S. (2012). Competitive Routing on a Bounded-Degree Plane Spanner. In

*Proceedings of the 24th Canadian Conference on Computational Geometry*(pp. 285-290)