Spatial data play an important role in many applications built over knowledge graphs, and are frequently referenced in queries posed to public query services, such as that of Wikidata.Querying for spatial data presents a significant challenge, as topological relations such as adjacent or contains imply inferred information, such as through the transitivity of the containment relation.However, despite all the recent advances in querying knowledge graphs, we still lack techniques specifically tailored for topological information.Applications looking to incorporate topological relations must either materialize the inferred relations, incurring high space and maintenance overheads, or query them with less efficient recursive algorithms, incurring high runtime overheads.In this paper we address the problem of leveraging topological information in knowledge graphs by designing efficient algorithms to process these queries.Our solution involves building a specific index that stores the topological information in a convenient compact form, and includes specialized algorithms that infer every possible relation from the basic topological facts in the graph.We show that, while using essentially the same space required to solve standard graph pattern queries, we can incorporate topological predicates, accounting for all the inferred information, all within worst-caseoptimal time.We implement our scheme and show experimentally that it outperforms baseline solutions by a notable margin.

Abstract In this work we address the problem of speeding up navigational queries over compact planar graphs. In particular, we work over one of the most practical representations for compact planar graphs, which is based on the decomposition of the graph into one arbitrary spanning tree and a second one induced by the former. We propose a new optimization model that captures the desired topological properties of the first spanning tree. For this model, we propose several heuristics, which we experimentally compare on our application domain. The experimental results support that the model indeed captures the main properties that allow us speeding up the main navigational queries over several benchmarks.