Succinct data structures for families of interval graphs

DOI10.1007/978-3-030-24766-9_1MaRDI QIDQ2285077zbMATH OpenOpenAlexFDO

Authors Hüseyin Acan, Sankardeep Chakraborty, Seungbum Jo, Srinivasa Rao Satti

Publication date 16 January 2020

Full work available at URL https://arxiv.org/abs/1902.09228

zbMATH Keywords

interval graphsspace-efficient data structuressuccinct encoding

Mathematics Subject Classification ID

Graph representations (geometric and intersection representations, etc.) (05C62) Graph algorithms (graph-theoretic aspects) (05C85) Data structures (68P05) Graph theory (including graph drawing) in computer science (68R10) Nonnumerical algorithms (68W05)

Abstract: We consider the problem of designing succinct data structures for interval graphs with $n$ vertices while supporting degree, adjacency, neighborhood and shortest path queries in optimal time in the $Theta(logn)$-bit word RAM model. The degree query reports the number of incident edges to a given vertex in constant time, the adjacency query returns true if there is an edge between two vertices in constant time, the neighborhood query reports the set of all adjacent vertices in time proportional to the degree of the queried vertex, and the shortest path query returns a shortest path in time proportional to its length, thus the running times of these queries are optimal. Towards showing succinctness, we first show that at least $nlogn-2nloglogn-O(n)$ bits are necessary to represent any unlabeled interval graph $G$ with $n$ vertices, answering an open problem of Yang and Pippenger [Proc. Amer. Math. Soc. 2017]. This is augmented by a data structure of size $nlogn+O(n)$ bits while supporting not only the aforementioned queries optimally but also capable of executing various combinatorial algorithms (like proper coloring, maximum independent set etc.) on the input interval graph efficiently. Finally, we extend our ideas to other variants of interval graphs, for example, proper/unit interval graphs, k-proper and k-improper interval graphs, and circular-arc graphs, and design succinct/compact data structures for these graph classes as well along with supporting queries on them efficiently.

Recommendations

• Succinct encodings for families of interval graphs
• Succinct Representations of Arbitrary Graphs
• Succinct encoding of arbitrary graphs
• Succinct permutation graphs
• Succinct representation of labeled graphs

Cited in

(24)

• Wheeler graphs: a framework for BWT-based data structures
• Succinct navigational oracles for families of intersection graphs on a circle
• Succinct representation for (non)deterministic finite automata
• Succinct data structures for series-parallel, block-cactus and 3-leaf power graphs
• Succinct representations for (non)deterministic finite automata
• Frameworks for designing in-place graph algorithms
• Intersection graphs of \(k\)-acyclic families of subtrees and relational database query processing.
• Succinct encodings for families of interval graphs
• Compact representation of interval graphs and circular-arc graphs of bounded degree and chromatic number
• Succinct permutation graphs
• Succinct posets
• scientific article; zbMATH DE number 177545 (Why is no real title available?)
• Deferred-query: An efficient approach for some problems on interval graphs
• Succinct data structures for chordal graphs
• Indexing graph search trees and applications
• Algorithms and Computation
• scientific article; zbMATH DE number 7765383 (Why is no real title available?)
• Succinct data structure for path graphs
• Succinct data structures for bounded clique-width graphs
• Efficient non-isomorphic graph enumeration algorithms for several intersection graph classes
• Succinct data structures for SP, block-cactus and \(3\)-leaf power graphs
• Closing the gap: minimum space optimal time distance labeling scheme for interval graphs
• The bend number of cocomparability graphs
• Space-efficient depth-first search via augmented succinct graph encodings

This page was built for publication: Succinct data structures for families of interval graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2285077)