<p>Follow-up work by Holm, Rotenberg and Thorup [1] showed that there exists a reachability oracle for planar graphs of size <span class="math-container">$O(n)$</span> and query time <span class="math-container">$O(1)$</span>. This is optimal also for trees (e.g., if the input is a star graph, then you need to know the orientation of every one of the <span class="math-container">$n-1$</span> edges).</p>

<p>[1] Holm, Jacob, Eva Rotenberg, and Mikkel Thorup. "Planar reachability in linear space and constant time." 2015 IEEE 56th Annual Symposium on Foundations of Computer Science. IEEE, 2015.</p>

CC BY-SA 4.0
2020-02-10T12:19:03.743Z
2020-02-10T12:19:03.743Z
smapers
<p>What is the best complexity for reachability queries on trees so far please? There is no constraint on the directions of the edges in the tree. According to Mikkel Thorup, there is an oracle of size <span class="math-container">$O(n\log n)$</span> which supports <span class="math-container">$O(1)$</span> query time for planar graphs. Do trees have better complexity?</p>

<graph-theory><graph-algorithms><tree><planar-graphs>
Reachability Query for Tree
yefi
# Reachability Query for Tree

(Asked by: username_0 on 2020-02-10)

What is the best complexity for reachability queries on trees so far please? There is no constraint on the directions of the edges in the tree. According to Mikkel Thorup, there is an oracle of size $O(n\log n)$ which supports $O(1)$ query time for planar graphs. Do trees have better complexity?

**Tags:** graph-theory, graph-algorithms, tree, planar-graphs

---

## 1 answers

### Answer by username_1 on 2020-02-10. Score: 3 | Accepted answer

Follow-up work by Holm, Rotenberg and Thorup [1] showed that there exists a reachability oracle for planar graphs of size $O(n)$ and query time $O(1)$. This is optimal also for trees (e.g., if the input is a star graph, then you need to know the orientation of every one of the $n-1$ edges).

[1] Holm, Jacob, Eva Rotenberg, and Mikkel Thorup. "Planar reachability in linear space and constant time." 2015 IEEE 56th Annual Symposium on Foundations of Computer Science. IEEE, 2015.


---

