{"id":"arxiv/2606.14656","url":"https://arxiv.org/abs/2606.14656","tags":["math.CO"],"score":0,"title":"Pairwise Compatibility Representations of Multidimensional Grid Graphs","domain":"math.CO","source":"arxiv","authors":["Sheikh Azizul Hakim","Md. Shamsuzzoha Bayzid"],"reviews":0,"subject":"math.CO","summary":"Pairwise compatibility graphs (PCGs) represent graph adjacency by an interval of leaf-to-leaf distances in a weighted tree. We study grid graphs under the PCG model and two natural extensions: multi-interval PCGs and OR-PCGs. First, we prove that every $d$-dimensional grid graph is a $(d-1)$-interval-PCG. The construction decomposes the grid into hyperplanes of constant coordinate sum and uses a large-base encoding so that distances between consecutive hyperplanes identify the coordinate direction of an edge. A pair of nearby code values is then merged into one interval, reducing the number…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-06-12","reactions":{}}