{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,2]],"date-time":"2025-12-02T18:42:16Z","timestamp":1764700936767,"version":"3.37.3"},"reference-count":32,"publisher":"Oxford University Press (OUP)","issue":"5","license":[{"start":{"date-parts":[[2022,2,25]],"date-time":"2022-02-25T00:00:00Z","timestamp":1645747200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/academic.oup.com\/journals\/pages\/open_access\/funder_policies\/chorus\/standard_publication_model"}],"funder":[{"DOI":"10.13039\/501100009500","name":"Bangladesh University of Engineering and Technology","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100009500","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2023,5,19]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>A graph $G = (V,E)$ is called a pairwise compatibility graph (PCG) if it admits a tuple $(T, d_{min},d_{max})$ of an edge-weighted tree $T$ of non-negative edge weights with leaf set $L$, two non-negative real numbers $d_{min} \\leq d_{max}$ such that each vertex $u^{\\prime} \\in V$ represents a leaf $u \\in L$ and $G$ has an edge $(u^{\\prime},v^{\\prime}) \\in E$ if and only if the distance between the two leaves $u$ and $v$ in the tree $T$ lies within interval $[d_{min}, d_{max}]$. It has been proven that not all graphs are PCGs. A graph $G$ is called a $k$-interval PCG if there exists an edge-weighted tree $T$ and $k$ mutually exclusive intervals of non-negative real numbers such that there is an edge between two vertices in $G$ if and only if the distance between their corresponding leaves in $T$ lies within any of the $k$ intervals. It is known that every graph $G$ is a $k$-interval PCG for $k=|E|$, where $E$ is the set of edges of $G$. It is thus interesting to know the smallest value of $k$ for which $G$ is a $k$-interval PCG. In this paper, we show that grid graphs and a subclass of $3$D grid graphs are $2$-interval PCGs.<\/jats:p>","DOI":"10.1093\/comjnl\/bxac011","type":"journal-article","created":{"date-parts":[[2022,1,25]],"date-time":"2022-01-25T04:12:13Z","timestamp":1643083933000},"page":"1256-1267","source":"Crossref","is-referenced-by-count":6,"title":["On 2-Interval Pairwise Compatibility Properties of Two Classes of Grid Graphs"],"prefix":"10.1093","volume":"66","author":[{"given":"Bishal Basak","family":"Papan","sequence":"first","affiliation":[{"name":"Graph Drawing and Information Visualization Laboratory , Department of Computer Science and Engineering, Bangladesh University of Engineering and Technology (BUET), Dhaka-1205, Bangladesh"}]},{"given":"Protik Bose","family":"Pranto","sequence":"additional","affiliation":[{"name":"Graph Drawing and Information Visualization Laboratory , Department of Computer Science and Engineering, Bangladesh University of Engineering and Technology (BUET), Dhaka-1205, Bangladesh"}]},{"given":"Md Saidur","family":"Rahman","sequence":"additional","affiliation":[{"name":"Graph Drawing and Information Visualization Laboratory , Department of Computer Science and Engineering, Bangladesh University of Engineering and Technology (BUET), Dhaka-1205, Bangladesh"}]}],"member":"286","published-online":{"date-parts":[[2022,2,25]]},"reference":[{"key":"2023052000434763100_ref1","doi-asserted-by":"crossref","first-page":"177","DOI":"10.1007\/978-3-540-39763-2_14","volume-title":"International Workshop on Algorithms in Bioinformatics","author":"Kearney","year":"2003"},{"key":"2023052000434763100_ref2","doi-asserted-by":"crossref","first-page":"212","DOI":"10.1016\/j.dam.2020.05.015","article-title":"Exact-2-relation graphs","volume":"285","author":"Long","year":"2020","journal-title":"Discrete. Appl. Math."},{"key":"2023052000434763100_ref3","doi-asserted-by":"crossref","first-page":"81","DOI":"10.7155\/jgaa.00286","article-title":"Triangle-free outerplanar 3-graphs are pairwise compatibility graphs","volume":"17","author":"Salma","year":"2013","journal-title":"J. Graph Algorithms Appl."},{"key":"2023052000434763100_ref4","doi-asserted-by":"crossref","first-page":"1616","DOI":"10.1093\/comjnl\/bxt068","article-title":"Pairwise Compatibility Graphs of Caterpillars","volume":"57","author":"Calamoneri","year":"2013","journal-title":"Comput. J."},{"key":"2023052000434763100_ref5","doi-asserted-by":"crossref","first-page":"882","DOI":"10.1093\/comjnl\/bxs087","article-title":"All Graphs with at Most Seven Vertices are Pairwise Compatibility Graphs","volume":"56","author":"Calamoneri","year":"2012","journal-title":"Comput. J."},{"article-title":"Uniform sampling from phylogenetic trees","year":"2002","author":"Phillips","key":"2023052000434763100_ref6"},{"key":"2023052000434763100_ref7","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1016\/j.tcs.2012.11.015","article-title":"Exploring pairwise compatibility graphs","volume":"468","author":"Calamoneri","year":"2013","journal-title":"Theor. Comput. Sci."},{"key":"2023052000434763100_ref8","doi-asserted-by":"crossref","first-page":"34","DOI":"10.1016\/j.tcs.2013.12.015","article-title":"On pairwise compatibility graphs having dilworth number two","volume":"524","author":"Calamoneri","year":"2014","journal-title":"Theor. Comput. Sci."},{"key":"2023052000434763100_ref9","doi-asserted-by":"crossref","first-page":"607","DOI":"10.1142\/S1793830910000917","article-title":"Discovering pairwise compatibility graphs","volume":"2","author":"Yanhaona","year":"2010","journal-title":"Discrete Math. Algorithms Appl."},{"key":"2023052000434763100_ref10","doi-asserted-by":"crossref","first-page":"479","DOI":"10.1007\/s12190-008-0204-7","article-title":"Pairwise compatibility graphs","volume":"30","author":"Yanhaona","year":"2009","journal-title":"J. Appl. Math. Comput."},{"key":"2023052000434763100_ref11","first-page":"124","volume-title":"Proceedings of 6th the International Workshop on Algorithm and Computation, Vol. 7157 of Lecture Notes in Computer Science","author":"Calamoneri","year":"2012"},{"key":"2023052000434763100_ref12","doi-asserted-by":"crossref","first-page":"788","DOI":"10.1016\/j.akcej.2019.12.011","article-title":"A survey on pairwise compatibility graphs","volume":"17","author":"Rahman","year":"2020","journal-title":"AKCE Int. J. Graphs Combinatorics"},{"key":"2023052000434763100_ref13","doi-asserted-by":"crossref","first-page":"445","DOI":"10.1137\/140978053","article-title":"Pairwise compatibility graphs: A survey","volume":"58","author":"Calamoneri","year":"2016","journal-title":"SIAM Rev."},{"key":"2023052000434763100_ref14","doi-asserted-by":"crossref","first-page":"78","DOI":"10.1016\/j.tcs.2015.01.011","article-title":"On graphs that are not PCGs","volume":"571","author":"Durocher","year":"2015","journal-title":"Theor. Comput. Sci."},{"key":"2023052000434763100_ref15","doi-asserted-by":"crossref","first-page":"1360002","DOI":"10.1142\/S1793830913600021","article-title":"On the pairwise compatibility property of some superclasses of threshold graphs","volume":"5","author":"Calamoneri","year":"2013","journal-title":"Discrete Math. Algorithms Appl."},{"key":"2023052000434763100_ref16","first-page":"39","volume-title":"Proceedings of 29th International Workshop on Combinatorial Algorithms, Vol. 10979 of Lecture Notes in Computer Science","author":"Baiocchi","year":"2018"},{"key":"2023052000434763100_ref17","doi-asserted-by":"crossref","first-page":"3066","DOI":"10.1007\/s00453-020-00712-8","article-title":"Characterizing star-PCGs","volume":"82","author":"Xiao","year":"2020","journal-title":"Algorithmica"},{"key":"2023052000434763100_ref18","doi-asserted-by":"crossref","first-page":"341","DOI":"10.7155\/jgaa.00419","article-title":"A necessary condition and a sufficient condition for pairwise compatibility graphs","volume":"21","author":"Hossain","year":"2017","journal-title":"J. Graph Algorithms Appl."},{"key":"2023052000434763100_ref19","doi-asserted-by":"crossref","first-page":"69","DOI":"10.1006\/jagm.2001.1195","article-title":"On graph powers for leaf-labeled trees","volume":"42","author":"Nishimura","year":"2002","journal-title":"J. Algorithms"},{"key":"2023052000434763100_ref20","first-page":"81","volume-title":"Stichting Mathematisch Centrum. Mathematische Besliskunde","author":"Kolen","year":"1981"},{"key":"2023052000434763100_ref21","doi-asserted-by":"crossref","first-page":"166","DOI":"10.1006\/jagm.1998.0962","article-title":"Distance approximating trees for chordal and dually chordal graphs","volume":"30","author":"Brandst\u00e4dt","year":"1999","journal-title":"J. Algorithms"},{"key":"2023052000434763100_ref22","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/1435375.1435386","article-title":"Structure and linear-time recognition of 4-leaf powers","volume":"5","author":"Brandst\u00e4dt","year":"2008","journal-title":"ACM Trans. Algorithms (TALG)"},{"key":"2023052000434763100_ref23","first-page":"479","volume-title":"Proceedings of 8th LATIN American Symposium, Theoretical Informatics, Vol. 4957 of Lecture Notes in Computer Science","author":"Brandst\u00e4dt","year":"2008"},{"key":"2023052000434763100_ref24","doi-asserted-by":"crossref","first-page":"897","DOI":"10.1016\/j.disc.2009.10.006","article-title":"Rooted directed path graphs are leaf powers","volume":"310","author":"Brandst\u00e4dt","year":"2010","journal-title":"Discrete Math."},{"key":"2023052000434763100_ref25","doi-asserted-by":"crossref","first-page":"511","DOI":"10.1016\/j.jda.2005.06.005","article-title":"Strictly chordal graphs are leaf powers","volume":"4","author":"Kennedy","year":"2006","journal-title":"J. Discrete Algorithms"},{"key":"2023052000434763100_ref26","first-page":"539","volume-title":"Proceedings of 11th International Conference on Algorithms and Computation, ISAAC, Vol. 1969 of Lecture Notes in Computer Science","author":"Lin","year":"2000"},{"key":"2023052000434763100_ref27","first-page":"43","volume-title":"Theor. Comput. Sci.","author":"Tsukiji","year":"2006"},{"key":"2023052000434763100_ref28","doi-asserted-by":"crossref","first-page":"2053","DOI":"10.1007\/s00373-016-1707-x","article-title":"Towards a characterization of leaf powers by clique arrangements","volume":"32","author":"Nevries","year":"2016","journal-title":"Graphs Combinatorics"},{"key":"2023052000434763100_ref29","first-page":"402","volume-title":"International Symposium on Algorithms and Computation, Vol. 5369 of Lecture Notes in Computer Science","author":"Fellows","year":"2008"},{"key":"2023052000434763100_ref30","first-page":"73","volume-title":"Proceedings of the 15th Italian Conference on Theoretical Computer Science","author":"Calamoneri","year":"2014"},{"key":"2023052000434763100_ref31","first-page":"71","volume-title":"Proceedings of 14th Annual Conference on Theory and Applications of Models of Computation, Vol. 10185 of Lecture Notes in Computer Science","author":"Ahmed","year":"2017"},{"key":"2023052000434763100_ref32","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-319-49475-3","volume-title":"Basic Graph Theory","author":"Rahman","year":"2017"}],"container-title":["The Computer Journal"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/comjnl\/article-pdf\/66\/5\/1256\/50397710\/bxac011.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/comjnl\/article-pdf\/66\/5\/1256\/50397710\/bxac011.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,20]],"date-time":"2023-05-20T00:46:23Z","timestamp":1684543583000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/comjnl\/article\/66\/5\/1256\/6536120"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,2,25]]},"references-count":32,"journal-issue":{"issue":"5","published-online":{"date-parts":[[2022,2,25]]},"published-print":{"date-parts":[[2023,5,19]]}},"URL":"https:\/\/doi.org\/10.1093\/comjnl\/bxac011","relation":{},"ISSN":["0010-4620","1460-2067"],"issn-type":[{"type":"print","value":"0010-4620"},{"type":"electronic","value":"1460-2067"}],"subject":[],"published-other":{"date-parts":[[2023,5]]},"published":{"date-parts":[[2022,2,25]]}}}