Succinct Permutation Graphs

Tsakalidis, Konstantinos ORCID: 0000-0001-6470-9332, Wild, Sebastian ORCID: 0000-0002-6061-9177 and Zamaraev, Viktor ORCID: 0000-0001-5755-4141 (2020) Succinct Permutation Graphs. [Report]

Text 2010.04108v1.pdf - Submitted version Download (406kB) | Preview

Abstract

We present a succinct data structure for permutation graphs, and their superclass of circular permutation graphs, i.e., data structures using optimal space up to lower order terms. Unlike concurrent work on circle graphs (Acan et al. 2022), our data structure also supports distance and shortest-path queries, as well as adjacency and neighborhood queries, all in optimal time. We present in particular the first succinct exact distance oracle for (circular) permutation graphs. A second succinct data structure also supports degree queries in time independent of the neighborhood's size at the expense of an $O(\log n/\log \log n)$-factor overhead in all running times. Furthermore, we develop a succinct data structure for the class of bipartite permutation graphs. We demonstrate how to run algorithms directly over our succinct representations for several problems on permutation graphs: Clique, Coloring, Independent Set, Hamiltonian Cycle, All-Pair Shortest Paths, and others. Finally, we initiate the study of semi-distributed graph representations; a concept that smoothly interpolates between distributed (labeling schemes) and centralized (standard data structures). We show how to turn some of our data structures into semi-distributed representations by storing only $O(n)$ bits of additional global information, circumventing the lower bound on distance labeling schemes for permutation graphs.

Item Type:	Report
Additional Information:	updated to match final Algorithmica version
Uncontrolled Keywords:	cs.DS, cs.DS, cs.DM
Depositing User:	Symplectic Admin
Date Deposited:	12 Oct 2020 14:58
Last Modified:	18 Jan 2023 23:29
Related URLs:	Author Publisher
URI:	https://livrepository.liverpool.ac.uk/id/eprint/3104049