2026-07-22T14:06:25Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:23486 2025-10-02T12:56:33Z ddc:004 open_access

Faster Diameter Computation in Graphs of Bounded Euler Genus Kluk, Kacper Pilipczuk, Marcin Pilipczuk, Michał Stamoulis, Giannos Diameter eccentricity subquadratic algorithms surface-embeddable graphs We show that for any fixed integer k ⩾ 0, there exists an algorithm that computes the diameter and the eccentricies of all vertices of an input unweighted, undirected n-vertex graph of Euler genus at most k in time 𝒪_k(n^{2-1/25}). Furthermore, for the more general class of graphs that can be constructed by clique-sums from graphs that are of Euler genus at most k after deletion of at most k vertices, we show an algorithm for the same task that achieves the running time bound 𝒪_k(n^{2-1/356} log^{6k} n). Up to today, the only known subquadratic algorithms for computing the diameter in those graph classes are that of [Ducoffe, Habib, Viennot; SICOMP 2022], [Le, Wulff-Nilsen; SODA 2024], and [Duraj, Konieczny, Potępa; ESA 2024]. These algorithms work in the more general setting of K_h-minor-free graphs, but the running time bound is 𝒪_h(n^{2-c_h}) for some constant c_h > 0 depending on h. That is, our savings in the exponent of the polynomial function of n, as compared to the naive quadratic algorithm, are independent of the parameter k. The main technical ingredient of our work is an improved bound on the number of distance profiles, as defined in [Le, Wulff-Nilsen; SODA 2024], in graphs of bounded Euler genus. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Kacper Kluk and Marcin Pilipczuk and Michał Pilipczuk and Giannos Stamoulis 2025 Is Part Of LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2025.109 urn:nbn:de:0030-drops-234869 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.109 eng https://creativecommons.org/licenses/by/4.0/legalcode