Exact Distance Oracles for Planar Graphs

Shay Mozes and Christian Sommer

Abstract:

We present new and improved data structures that answer exact node-to-node distance queries in planar graphs. Such data structures are also known as distance oracles. For any directed planar graph on n nodes with non-negative lengths we obtain the following:

  • Given a desired space allocation S \in \[ n \log\log n, n^2 \], we show how to construct in time a data structure of size O(S) that answers distance queries in time per query. As a consequence, we obtain an improvement over the fastest algorithm for k-many distances in planar graphs whenever .
  • We provide a linear-space exact distance oracle for planar graphs with query time for any constant . This is the first such data structure with provable sublinear query time.
  • For edge lengths , we provide an exact distance oracle of space such that for any pair of nodes at distance the query time is . Comparable query performance had been observed experimentally but could not be proven.

Our data structures are based on the following new tool: given a non-self-crossing cycle C with nodes, we can preprocess G in time to produce a data structure of size that can answer the following queries in time: for a query node u, output the distance from u to all the nodes of C. This data structure builds on and extends a related data structure of Klein (SODA’05), which reports distances to the boundary of a face, rather than a cycle.
The best distance oracles for planar graphs until the current work are due to Cabello (SODA’06), Djidjev (WG’96), and Fakcharoenphol and Rao (FOCS’01). For and space , we essentially improve the query time from to .

Guest: Shay Mozes
Host: Shantanu Das

Leave a Reply

Your email address will not be published.

164,523 Spam Comments Blocked so far by Spam Free Wordpress

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>