Pairwise Compatibility Representations of Multidimensional Grid Graphs
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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2606.14656
curl -X POST /api/v1/records/arxiv/2606.14656/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2606.14656/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'