Real-weighted diameter and eccentricities of minor-free and bounded VC-dimension graphs in truly subquadratic time LIPIcs Zheng, Da Wei Diameter eccentricities minor-free graphs real weights VC-dimension ddc:000 We present the first truly subquadratic time algorithm to compute diameter and eccentricities in real-weighted directed graphs with constant distance VC-dimension and strongly sublinear-sized balanced separators. For real-weighted K_h-minor-free digraphs, this runs in O(n^{2-1/(2h-2)} polylog(n)) time. Prior to this work, truly subquadratic time computation of diameter was only known for real-weighted planar graphs, while extensions to broader classes like minor-free graphs were restricted to unweighted settings. In particular, existing algorithms that use VC-dimension [Ducoffe, Habib, Viennot; SICOMP 2022] [Le, Wulff-Nilsen; SODA 2024] [Chan, Chang, Gao, Le, Kisfaludi-Bak, Zheng; FOCS 2025] work with small integer weights, but do not naturally generalize to real weights. We overcome this barrier by introducing a randomized search-to-decision reduction, demonstrating that VC-dimension is a sufficiently powerful tool in the real-weighted regime. Schloss Dagstuhl - Leibniz-Zentrum für Informatik 2026 info:eu-repo/semantics/conferenceObject doc-type:ConferenceObject ConferenceObject http://purl.org/coar/resource_type/c_5794 https://research-explorer.ista.ac.at/record/22914 https://research-explorer.ista.ac.at/download/22914/22942 Zheng DW. Real-weighted diameter and eccentricities of minor-free and bounded VC-dimension graphs in truly subquadratic time. In: <i>34th Annual European Symposium on Algorithms</i>. Vol 388. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2026. doi:<a href="https://doi.org/10.4230/LIPIcs.ESA.2026.61">10.4230/LIPIcs.ESA.2026.61</a> eng info:eu-repo/semantics/altIdentifier/doi/10.4230/LIPIcs.ESA.2026.61 info:eu-repo/semantics/altIdentifier/e-issn/1868-8969 info:eu-repo/semantics/altIdentifier/isbn/9783959774451 info:eu-repo/semantics/altIdentifier/arxiv/2607.01926 info:eu-repo/semantics/openAccess