{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,2]],"date-time":"2026-01-02T07:38:58Z","timestamp":1767339538673,"version":"3.40.5"},"reference-count":38,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2022,9,24]],"date-time":"2022-09-24T00:00:00Z","timestamp":1663977600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,9,24]],"date-time":"2022-09-24T00:00:00Z","timestamp":1663977600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2023,2]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>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. in Theor Comput Sci, <jats:ext-link xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" ext-link-type=\"doi\" xlink:href=\"10.1016\/j.tcs.2022.06.022\">https:\/\/doi.org\/10.1016\/j.tcs.2022.06.022<\/jats:ext-link>, 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\u2019s size at the expense of an <jats:inline-formula><jats:alternatives><jats:tex-math>$$O(\\log n\/\\log \\log n)$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>O<\/mml:mi>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:mo>log<\/mml:mo>\n                    <mml:mi>n<\/mml:mi>\n                    <mml:mo>\/<\/mml:mo>\n                    <mml:mo>log<\/mml:mo>\n                    <mml:mo>log<\/mml:mo>\n                    <mml:mi>n<\/mml:mi>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-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: <jats:sc>Clique<\/jats:sc>, <jats:sc>Coloring<\/jats:sc>, <jats:sc>Independent Set<\/jats:sc>, <jats:sc>Hamiltonian Cycle<\/jats:sc>, <jats:sc>All-Pair Shortest Paths<\/jats:sc>, and others. Finally, we initiate the study of <jats:italic>semi-distributed<\/jats:italic> 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 <jats:inline-formula><jats:alternatives><jats:tex-math>$$O(n)$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>O<\/mml:mi>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:mi>n<\/mml:mi>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> bits of additional global information, circumventing the lower bound on distance labeling schemes for permutation graphs.<\/jats:p>","DOI":"10.1007\/s00453-022-01039-2","type":"journal-article","created":{"date-parts":[[2022,9,24]],"date-time":"2022-09-24T10:03:01Z","timestamp":1664013781000},"page":"509-543","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Succinct Permutation Graphs"],"prefix":"10.1007","volume":"85","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-6470-9332","authenticated-orcid":false,"given":"Konstantinos","family":"Tsakalidis","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6061-9177","authenticated-orcid":false,"given":"Sebastian","family":"Wild","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5755-4141","authenticated-orcid":false,"given":"Viktor","family":"Zamaraev","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,9,24]]},"reference":[{"key":"1039_CR1","doi-asserted-by":"crossref","unstructured":"Acan, H., Chakraborty, S., Jo, S., Nakashima, K., Sadakane, K., Satti, S.R.: Succinct navigational oracles for families of intersection graphs on a circle. arXiv:2010.04333 (2020)","DOI":"10.1109\/DCC50243.2021.00020"},{"key":"1039_CR2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2022.06.022","author":"H Acan","year":"2022","unstructured":"Acan, H., Chakraborty, S., Jo, S., Nakashima, K., Sadakane, K., Satti, S.R.: Succinct navigational oracles for families of intersection graphs on a circle. Theor. Comput. Sci. (2022). https:\/\/doi.org\/10.1016\/j.tcs.2022.06.022","journal-title":"Theor. Comput. Sci."},{"key":"1039_CR3","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-020-00710-w","author":"H Acan","year":"2020","unstructured":"Acan, H., Chakraborty, S., Jo, S., Rao Satti, S.: Succinct encodings for families of interval graphs. Algorithmica (2020). https:\/\/doi.org\/10.1007\/s00453-020-00710-w","journal-title":"Algorithmica"},{"issue":"11","key":"1039_CR4","doi-asserted-by":"publisher","first-page":"3465","DOI":"10.1016\/j.disc.2007.12.091","volume":"309","author":"F Bazzaro","year":"2009","unstructured":"Bazzaro, F., Gavoille, C.: Localized and compact data-structure for comparability graphs. Discret. Math. 309(11), 3465\u20133484 (2009). https:\/\/doi.org\/10.1016\/j.disc.2007.12.091","journal-title":"Discret. Math."},{"key":"1039_CR5","doi-asserted-by":"publisher","unstructured":"Bose, P., He, M., Maheshwari, A., Morin, P.: Succinct orthogonal range search structures on a grid with applications to text indexing. In: Workshop on Algorithms and Data Structures (WADS), pp. 98\u2013109. Springer, Berlin, Heidelberg (2009) https:\/\/doi.org\/10.1007\/978-3-642-03367-4_9","DOI":"10.1007\/978-3-642-03367-4_9"},{"issue":"3","key":"1039_CR6","doi-asserted-by":"publisher","first-page":"159","DOI":"10.1016\/s0166-218x(98)00145-0","volume":"102","author":"HS Chao","year":"2000","unstructured":"Chao, H.S., Hsu, F.R., Lee, R.C.T.: An optimal algorithm for finding the minimum cardinality dominating set on permutation graphs. Discret. Appl. Math. 102(3), 159\u2013173 (2000). https:\/\/doi.org\/10.1016\/s0166-218x(98)00145-0","journal-title":"Discret. Appl. Math."},{"key":"1039_CR7","unstructured":"Clark, D.R.: Compact PAT Trees. Ph.d. thesis (1996)"},{"issue":"1","key":"1039_CR8","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1002\/net.3230110103","volume":"11","author":"CJ Colbourn","year":"1981","unstructured":"Colbourn, C.J.: On testing isomorphism of permutation graphs. Networks 11(1), 13\u201321 (1981). https:\/\/doi.org\/10.1002\/net.3230110103","journal-title":"Networks"},{"issue":"2","key":"1039_CR9","doi-asserted-by":"publisher","first-page":"405","DOI":"10.1007\/s00453-008-9273-0","volume":"58","author":"C Crespelle","year":"2010","unstructured":"Crespelle, C., Paul, C.: Fully dynamic algorithm for recognition and modular decomposition of permutation graphs. Algorithmica 58(2), 405\u2013432 (2010)","journal-title":"Algorithmica"},{"issue":"2","key":"1039_CR10","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1007\/s11786-017-0294-4","volume":"11","author":"P Davoodi","year":"2017","unstructured":"Davoodi, P., Raman, R., Satti, S.R.: On succinct representations of binary trees. Math. Comput. Sci. 11(2), 177\u2013189 (2017). https:\/\/doi.org\/10.1007\/s11786-017-0294-4","journal-title":"Math. Comput. Sci."},{"issue":"3","key":"1039_CR11","doi-asserted-by":"publisher","first-page":"520","DOI":"10.1137\/s0097539791200375","volume":"23","author":"JS Deogun","year":"1994","unstructured":"Deogun, J.S., Steiner, G.: Polynomial algorithms for hamiltonian cycle in cocomparability graphs. SIAM J. Comput. 23(3), 520\u2013552 (1994). https:\/\/doi.org\/10.1137\/s0097539791200375","journal-title":"SIAM J. Comput."},{"key":"1039_CR12","doi-asserted-by":"crossref","unstructured":"Dodis, Y., P\u0103tra\u015fcu, M., Thorup, M.: Changing base without losing space. In: Proceedings of the Forty-Second ACM Symposium on Theory of Computing, pp. 593\u2013602 (2010)","DOI":"10.1145\/1806689.1806771"},{"issue":"3","key":"1039_CR13","doi-asserted-by":"publisher","first-page":"600","DOI":"10.2307\/2371374","volume":"63","author":"B Dushnik","year":"1941","unstructured":"Dushnik, B., Miller, E.W.: Partially ordered sets. Am. J. Math. 63(3), 600\u2013610 (1941)","journal-title":"Am. J. Math."},{"issue":"2","key":"1039_CR14","doi-asserted-by":"publisher","first-page":"465","DOI":"10.1137\/090779759","volume":"40","author":"J Fischer","year":"2011","unstructured":"Fischer, J., Heun, V.: Space-efficient preprocessing schemes for range minimum queries on static arrays. SIAM J. Comput. 40(2), 465\u2013492 (2011). https:\/\/doi.org\/10.1137\/090779759","journal-title":"SIAM J. Comput."},{"key":"1039_CR15","doi-asserted-by":"publisher","unstructured":"Gabow, H.N., Bentley, J.L., Tarjan, R.E.: Scaling and related techniques for geometry problems. In: Symposium on Theory of Computation (STOC). ACM Press (1984) https:\/\/doi.org\/10.1145\/800057.808675","DOI":"10.1145\/800057.808675"},{"issue":"3","key":"1039_CR16","doi-asserted-by":"publisher","first-page":"1239","DOI":"10.1137\/050635006","volume":"22","author":"C Gavoille","year":"2008","unstructured":"Gavoille, C., Paul, C.: Optimal distance labeling for interval graphs and related graph families. SIAM J. Discret. Math. 22(3), 1239\u20131258 (2008). https:\/\/doi.org\/10.1137\/050635006","journal-title":"SIAM J. Discret. Math."},{"key":"1039_CR17","doi-asserted-by":"publisher","unstructured":"Gog, S., Beller, T., Moffat, A., Petri, M.: From theory to practice: plug and play with succinct data structures. In: International Symposium on Experimental Algorithms (SEA), pp. 326\u2013337. https:\/\/doi.org\/10.1007\/978-3-319-07959-2_28 (2014)","DOI":"10.1007\/978-3-319-07959-2_28"},{"key":"1039_CR18","doi-asserted-by":"publisher","unstructured":"Gustedt, J., Morvan, M., Viennot, L.: A compact data structure and parallel algorithms for permutation graphs. In: Graph-Theoretic Concepts in Computer Science, pp. 372\u2013380. Springer Berlin, Heidelberg. https:\/\/doi.org\/10.1007\/3-540-60618-1_89 (1995)","DOI":"10.1007\/3-540-60618-1_89"},{"key":"1039_CR19","unstructured":"He, M., Munro, J.I., Nekrich, Y., Wild, S., Wu, K.: Breadth-first rank\/select in succinct trees and distance oracles for interval graphs. arXiv:2005.07644 (2020)"},{"key":"1039_CR20","doi-asserted-by":"crossref","unstructured":"Jacobson, G.: Space-efficient static trees and graphs. In: Symposium on Foundations of Computer Science (FOCS), pp. 549\u2013554 (1989)","DOI":"10.1109\/SFCS.1989.63533"},{"key":"1039_CR21","volume-title":"The Art Of Computer Programming: Searching and Sorting","author":"DE Knuth","year":"1998","unstructured":"Knuth, D.E.: The Art Of Computer Programming: Searching and Sorting, 2nd edn. Addison Wesley, New York (1998)","edition":"2"},{"issue":"1\u20133","key":"1039_CR22","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1016\/s0012-365x(98)00319-7","volume":"201","author":"RM McConnell","year":"1999","unstructured":"McConnell, R.M., Spinrad, J.P.: Modular decomposition and transitive orientation. Discret. Math. 201(1\u20133), 189\u2013241 (1999). https:\/\/doi.org\/10.1016\/s0012-365x(98)00319-7","journal-title":"Discret. Math."},{"key":"1039_CR23","doi-asserted-by":"publisher","unstructured":"M\u00f6hring, R.H.: Algorithmic aspects of comparability graphs and interval graphs. In: Graphs and Order, pp. 41\u2013101. Springer, Netherlands. https:\/\/doi.org\/10.1007\/978-94-009-5315-4_2 (1985)","DOI":"10.1007\/978-94-009-5315-4_2"},{"issue":"1","key":"1039_CR24","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1023\/A:1023695531209","volume":"2","author":"S Mondal","year":"2003","unstructured":"Mondal, S., Pal, M., Pal, T.K.: An optimal algorithm to solve the all-pairs shortest paths problem on permutation graphs. J. Math. Model. Algor. 2(1), 57\u201365 (2003)","journal-title":"J. Math. Model. Algor."},{"key":"1039_CR25","doi-asserted-by":"publisher","unstructured":"Munro, J.I., Wu, K.: Succinct data structures for chordal graphs. In: 29th International Symposium on Algorithms and Computation, ISAAC 2018, December 16\u201319, 2018, Jiaoxi, Yilan, Taiwan, pp. 67:1\u201367:12. https:\/\/doi.org\/10.4230\/LIPIcs.ISAAC.2018.67 (2018)","DOI":"10.4230\/LIPIcs.ISAAC.2018.67"},{"key":"1039_CR26","unstructured":"Munro, J.I., Wu, K.: Succinct data structures for chordal graphs. In: 29th International Symposium on Algorithms and Computation (ISAAC 2018). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik (2018)"},{"key":"1039_CR27","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781316588284","volume-title":"Compact Data Structures\u2014A practical approach","author":"G Navarro","year":"2016","unstructured":"Navarro, G.: Compact Data Structures\u2014A practical approach. Cambridge University Press, Cambridge (2016)"},{"key":"1039_CR28","doi-asserted-by":"publisher","unstructured":"P\u0103tra\u015fcu, M.: Succincter. In: Symposium on Foundations of Computer Science (FOCS). IEEE. https:\/\/doi.org\/10.1109\/focs.2008.83 (2008)","DOI":"10.1109\/focs.2008.83"},{"issue":"1","key":"1039_CR29","doi-asserted-by":"publisher","first-page":"160","DOI":"10.4153\/cjm-1971-016-5","volume":"23","author":"A Pnueli","year":"1971","unstructured":"Pnueli, A., Lempel, A., Even, S.: Transitive orientation of graphs and identification of permutation graphs. Can. J. Math. 23(1), 160\u2013175 (1971). https:\/\/doi.org\/10.4153\/cjm-1971-016-5","journal-title":"Can. J. Math."},{"issue":"4","key":"1039_CR30","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1145\/1290672.1290680","volume":"3","author":"R Raman","year":"2007","unstructured":"Raman, R., Raman, V., Rao Satti, S.: Succinct indexable dictionaries with applications to encoding k-ary trees, prefix sums and multisets. ACM Trans. Algorithms 3(4), 43 (2007). https:\/\/doi.org\/10.1145\/1290672.1290680","journal-title":"ACM Trans. Algorithms"},{"issue":"4","key":"1039_CR31","doi-asserted-by":"publisher","first-page":"429","DOI":"10.1002\/net.3230120407","volume":"12","author":"D Rotem","year":"1982","unstructured":"Rotem, D., Urrutia, J.: Circular permutation graphs. Networks 12(4), 429\u2013437 (1982). https:\/\/doi.org\/10.1002\/net.3230120407","journal-title":"Networks"},{"key":"1039_CR32","doi-asserted-by":"publisher","first-page":"84","DOI":"10.1016\/j.jda.2011.11.001","volume":"10","author":"T Saitoh","year":"2012","unstructured":"Saitoh, T., Otachi, Y., Yamanaka, K., Uehara, R.: Random generation and enumeration of bipartite permutation graphs. J. Discrete Algorithms 10, 84\u201397 (2012). https:\/\/doi.org\/10.1016\/j.jda.2011.11.001","journal-title":"J. Discrete Algorithms"},{"key":"1039_CR33","doi-asserted-by":"publisher","DOI":"10.1016\/j.aim.2021.107593","volume":"380","author":"L Sauermann","year":"2021","unstructured":"Sauermann, L.: On the speed of algebraically defined graph classes. Adv. Math. 380, 107593 (2021)","journal-title":"Adv. Math."},{"key":"1039_CR34","volume-title":"Algorithms","author":"R Sedgewick","year":"2011","unstructured":"Sedgewick, R., Wayne, K.: Algorithms, 4th edn. Addison-Wesley, New York (2011)","edition":"4"},{"issue":"3","key":"1039_CR35","doi-asserted-by":"publisher","first-page":"279","DOI":"10.1016\/S0166-218X(87)80003-3","volume":"18","author":"J Spinrad","year":"1987","unstructured":"Spinrad, J., Brandst\u00e4dt, A., Stewart, L.: Bipartite permutation graphs. Discret. Appl. Math. 18(3), 279\u2013292 (1987)","journal-title":"Discret. Appl. Math."},{"issue":"3","key":"1039_CR36","doi-asserted-by":"publisher","first-page":"171","DOI":"10.1002\/(sici)1097-0037(199605)27:3<171::aid-net1>3.0.co;2-f","volume":"27","author":"R Sritharan","year":"1996","unstructured":"Sritharan, R.: A linear time algorithm to recognize circular permutation graphs. Networks 27(3), 171\u2013174 (1996). https:\/\/doi.org\/10.1002\/(sici)1097-0037(199605)27:3<171::aid-net1>3.0.co;2-f","journal-title":"Networks"},{"key":"1039_CR37","unstructured":"Tsakalidis, K., Wild, S., Zamaraev, V.: Succinct permutation graphs. arXiv:2010.04108 (2020)"},{"issue":"4","key":"1039_CR38","doi-asserted-by":"publisher","first-page":"229","DOI":"10.1145\/358841.358852","volume":"23","author":"J Vuillemin","year":"1980","unstructured":"Vuillemin, J.: A unifying look at data structures. Commun. ACM 23(4), 229\u2013239 (1980). https:\/\/doi.org\/10.1145\/358841.358852","journal-title":"Commun. ACM"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-022-01039-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-022-01039-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-022-01039-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,27]],"date-time":"2023-01-27T09:18:38Z","timestamp":1674811118000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-022-01039-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,9,24]]},"references-count":38,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2023,2]]}},"alternative-id":["1039"],"URL":"https:\/\/doi.org\/10.1007\/s00453-022-01039-2","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2022,9,24]]},"assertion":[{"value":"1 September 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"10 September 2022","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"24 September 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}