Compact representation of interval graphs and circular-arc graphs of bounded degree and chromatic number

DOI10.1016/j.tcs.2022.11.010OpenAlexW4310061560MaRDI QIDQ2680858

Seungbum Jo, Sankardeep Chakraborty

Publication date: 4 January 2023

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2022.11.010

zbMATH Keywords

interval graphscircular-arc graphscompact data structuresnavigational queries

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Related Items (1)

Succinct data structure for path graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Ultra-succinct representation of ordered trees with applications
• Efficient graph representations
• Interval degree and bandwidth of a graph
• Linear-time recognition of circular-arc graphs
• Algorithmic graph theory and perfect graphs
• Compressed range minimum queries
• Succinct encodings for families of interval graphs
• Interval Graphs: Canonical Representations in Logspace
• Succinct Orthogonal Range Search Structures on a Grid with Applications to Text Indexing
• Optimal Distance Labeling for Interval Graphs and Related Graph Families
• Rank/select operations on large alphabets
• Counting Interval Graphs
• The Complexity of Coloring Circular Arcs and Chords
• Fast and compact planar embeddings

This page was built for publication: Compact representation of interval graphs and circular-arc graphs of bounded degree and chromatic number