2026-07-23T19:06:13Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:23921 2026-02-09T06:24:00Z ddc:004 open_access

Graph Indexing Beyond Wheeler Graphs Alanko, Jarno N. Biagi, Elena Equi, Massimo Mäkinen, Veli Puglisi, Simon J. Rizzo, Nicola Sadakane, Kunihiko Sirén, Jouni indexing compression compressed data structures string algorithms pattern matching After the discovery of the FM index, which linked the Burrows-Wheeler transform (BWT) to pattern matching on strings, several contemporaneous strands of research began on indexing more complex structures with the BWT, such as tries, finite languages, de Bruijn graphs, and aligned sequences. These directions can now be viewed as culminating in the theory of Wheeler Graphs, but sometimes they go beyond. This chapter reviews the significant body of "proto Wheeler Graph" indexes, many of which exploit characteristics of their specific case to outperform Wheeler graphs, especially in practice. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Jarno N. Alanko and Elena Biagi and Massimo Equi and Veli Mäkinen and Simon J. Puglisi and Nicola Rizzo and Kunihiko Sadakane and Jouni Sirén 2025 Is Part Of OASIcs, Volume 131, The Expanding World of Compressed Data: A Festschrift for Giovanni Manzini's 60th Birthday (2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/OASIcs.Manzini.13 urn:nbn:de:0030-drops-239215 https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.Manzini.13 eng https://creativecommons.org/licenses/by/4.0/legalcode