Succinct navigational oracles for families of intersection graphs on a circle

DOI10.1016/j.tcs.2022.06.022OpenAlexW3092339751MaRDI QIDQ2079878

Seungbum Jo, Kei Nakashima, Kunihiko Sadakane, Hüseyin Acan, Srinivasa Rao Satti, Sankardeep Chakraborty

Publication date: 7 October 2022

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

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

zbMATH Keywords

intersection graphsuccinct data structurenavigational query

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Related Items (2)

Succinct permutation graphs ⋮ Succinct data structure for path graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Succinct encoding of arbitrary graphs
• Compact navigation and distance oracles for graphs with small treewidth
• Efficient fully-compressed sequence representations
• Trapezoid graphs and generalizations, geometry and algorithms
• Succinct representations of planar maps
• Localized and compact data-structure for comparability graphs
• Interval graphs and related topics
• Efficient graph representations
• Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing
• Polygon-circle and word-representable graphs
• Algorithmic graph theory and perfect graphs
• Vertex splitting and the recognition of trapezoid graphs
• Succinct data structures for families of interval graphs
• Connected permutation graphs
• Succinct Representation of Balanced Parentheses and Static Trees
• Space-Efficient Preprocessing Schemes for Range Minimum Queries on Static Arrays
• Succinct Orthogonal Range Search Structures on a Grid with Applications to Text Indexing
• Optimal Distance Labeling for Interval Graphs and Related Graph Families
• Recognition of Polygon-Circle Graphs and Graphs of Interval Filaments Is NP-Complete
• On the Redundancy of Succinct Data Structures
• Topics in Intersection Graph Theory
• Recognition of Circle Graphs
• Graph Drawing
• Algorithms for a maximum clique and a maximum independent set of a circle graph

This page was built for publication: Succinct navigational oracles for families of intersection graphs on a circle