# Reconstructing Bounded Treelength Graphs with Linearithmic Shortest Path Distance Queries

Preprint · Chirag Kaudan, Amir Nayyeri

- Archive id: arxiv:2603.10432
- Published: 2026-03-11
- Venue: Proceedings of the 37th Canadian Conference on Computational Geometry (2025) pp 243-248
- arXiv: https://arxiv.org/abs/2603.10432
- Source URL: https://arxiv.org/abs/2603.10432
- PDF: https://arxiv.org/pdf/2603.10432
- Provenance: arxiv

## Abstract

We consider the following graph reconstruction problem: given an unweighted connected graph $G = (V,E)$ with visible vertex set $V$ and an oracle which takes two vertices $u,v \\in V$ and returns the shortest path distance between $u$ and $v$, how many queries are needed to reconstruct $E$? Specifically, we consider bounded degree $Δ$ and bounded treelength $\\mathrm{tl}$ connected graphs and show that reconstruction can be done in $O\_{Δ,\\mathrm{tl}}(n \\log n)$ queries with a deterministic algorithm. This result improves over the best known algorithm (deterministic or randomized) for this graph class by a $\\log n$ factor and matches the known lower bound for the class of graphs with bounded chordality, which is a subclass of bounded treelength graphs.

_Abstract reproduced under CC0-1.0 (arXiv descriptive metadata)._

---
Space Kitty Archive · https://space-kitty.com · API: https://space-kitty.com/api/v1 · MCP: https://space-kitty.com/mcp · Premium: $0.20/request via x402 (Base Sepolia (testnet)). Metadata: arXiv (CC0), OpenAlex (CC0), Europe PMC (CC BY/CC0 works), ClinicalTrials.gov.