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. Towards showing succinctness, we first show that at least \(n\log _2{n} - 2n\log _2\log _2 n - 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 \(n\log _2{n} +O(n)\) bits while supporting not only the above queries optimally but also capable of executing various combinatorial algorithms (like proper coloring, maximum independent set etc.) on interval graphs efficiently. Finally, we extend our ideas to other variants of interval graphs, for example, proper/unit, k-improper interval graphs, and circular-arc graphs, and design succinct data structures for these graph classes as well along with supporting queries on them efficiently.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
Throughout the paper, we use \(\log \) to denote the logarithm to the base 2.
References
Aleardi, L.C., Devillers, O., Schaeffer, G.: Succinct representations of planar maps. Theor. Comput. Sci. 408(2–3), 174–187 (2008)
Bar-Noy, A., Bar-Yehuda, R., Freund, A., Naor, J., Schieber, B.: A unified approach to approximating resource allocation and scheduling. J. ACM 48(5), 1069–1090 (2001)
Benser, S.: On the topology of the genetic fine structure. Proc. Nat. Acad. Sci. 45, 1607–1620 (1959)
Booth, K.S., Lueker, G.S.: Testing for the consecutive ones property, interval graphs, and graph planarity using pq-tree algorithms. J. Comput. Syst. Sci. 13(3), 335–379 (1976)
Bose, P., He, M., Maheshwari, A., Morin, P.: Succinct orthogonal range search structures on a grid with applications to text indexing. In: Dehne, F., Gavrilova, M., Sack, J.-R., Tóth, C.D. (eds.) WADS 2009. LNCS, vol. 5664, pp. 98–109. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-03367-4_9
Brodal, G.S., Davoodi, P., Rao, S.S.: On space efficient two dimensional range minimum data structures. Algorithmica 63(4), 815–830 (2012)
Chen, D.Z., Lee, D.T., Sridhar, R., Sekharan, C.N.: Solving the all-pair shortest path query problem on interval and circular-arc graphs. Networks 31(4), 249–258 (1998)
Clark, D.R., Munro, J.I.: Efficient suffix trees on secondary storage. In: Proceedings of the Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 383–391 (1996)
Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms, 3rd edn. MIT Press, Cambridge (2009)
Diestel, R.: Graph Theory. Graduate Texts in Mathematics, vol. 173, 4th edn. Springer, Heidelberg (2012)
Farzan, A., Kamali, S.: Compact navigation and distance oracles for graphs with small treewidth. Algorithmica 69(1), 92–116 (2014)
Farzan, A., Munro, J.I.: Succinct encoding of arbitrary graphs. Theor. Comput. Sci. 513, 38–52 (2013)
Finch, S.R.: Mathematical Constants. Cambridge University Press, Cambridge (2003)
Fischer, J., Heun, V.: Space-efficient preprocessing schemes for range minimum queries on static arrays. SIAM J. Comput. 40(2), 465–492 (2011)
Golumbic, M.C.: Interval graphs and related topics. Discrete Math. 55(2), 113–121 (1985)
Golumbic, M.C.: Algorithmic Graph Theory and Perfect Graphs (2004)
Golumbic, M.C., Shamir, R.: Complexity and algorithms for reasoning about time: a graph-theoretic approach. J. ACM 40(5), 1108–1133 (1993)
Golynski, A., Munro, J.I., Rao, S.S.: Rank/select operations on large alphabets: a tool for text indexing. In: Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2006, pp. 368–373 (2006)
Habib, M., McConnell, R.M., Paul, C., Viennot, L.: Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing. Theor. Comput. Sci. 234(1–2), 59–84 (2000)
Hajós, G.: Über eine art von graphen. Int. Math. Nachr. 11, 1607–1620
Hanlon, P.: Counting interval graphs. Trans. Am. Math. Soc. 272(2), 383–426 (1982)
Klavzar, S., Petkovsek, M.: Intersection graphs of halflines and halfplanes. Discrete Math. 66(1–2), 133–137 (1987)
Munro, J.I., Raman, V.: Succinct representation of balanced parentheses and static trees. SIAM J. Comput. 31(3), 762–776 (2001)
Munro, J.I., Wu, K.: Succinct data structures for chordal graphs. In: 29th International Symposium on Algorithms and Computation, ISAAC 2018, pp. 67:1–67:12 (2018). https://doi.org/10.4230/LIPIcs.ISAAC.2018.67
Roberts, F.S.: Indifference graphs. In: Harary, F. (ed.) Proof Techniques in Graph Theory (1969)
Sloane, N.J.E.: The on-line encyclopedia of integer sequences. http://oeis.org
Yang, J.C., Pippenger, N.: On the enumeration of interval graphs. Proc. Am. Math. Soc. Ser. B 4(1), 1–3 (2017)
Zhang, P., et al.: An algorithm based on graph theory for the assembly of contigs in physical mapping of DNA. Bioinformatics 10(3), 309–317 (1994)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2019 Springer Nature Switzerland AG
About this paper
Cite this paper
Acan, H., Chakraborty, S., Jo, S., Satti, S.R. (2019). Succinct Data Structures for Families of Interval Graphs. In: Friggstad, Z., Sack, JR., Salavatipour, M. (eds) Algorithms and Data Structures. WADS 2019. Lecture Notes in Computer Science(), vol 11646. Springer, Cham. https://doi.org/10.1007/978-3-030-24766-9_1
Download citation
DOI: https://doi.org/10.1007/978-3-030-24766-9_1
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-24765-2
Online ISBN: 978-3-030-24766-9
eBook Packages: Computer ScienceComputer Science (R0)