Irribarra-Cortés, AyleenAsín-Achá, RobertoFuentes Sepúlveda, JoséSeco, Diego2025-11-122025-11-122025-05-14Ayleen Irribarra-Cortés, Roberto Asín-Achá, José Fuentes-Sepúlveda, Diego Seco, Heuristic-based computation of tailored spanning trees to speed up compact planar graphs, The Computer Journal, Volume 68, Issue 10, October 2025, Pages 1476–1484, https://doi.org/10.1093/comjnl/bxaf0511460-2067https://hdl.handle.net/2183/46415This is a pre-copyedited, author-produced version of an article accepted for publication in The Computer Journal following peer review. The version of record Ayleen Irribarra-Cortés, Roberto Asín-Achá, José Fuentes-Sepúlveda, Diego Seco, Heuristic-based computation of tailored spanning trees to speed up compact planar graphs, The Computer Journal, Volume 68, Issue 10, October 2025, Pages 1476–1484, is available online at: https://doi.org/10.1093/comjnl/bxaf051 The data and code of this article are available on public repositories. The implementation is available at the GitHub repository mentioned in Section 4.1. The datasets are available in the repository mentioned on Section 4.2.[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.eng© The British Computer Society 2025Compact data structurePlanar graphCombinatorial optimizationHeuristicsjournal articleopen access10.1093/comjnl/bxaf051