Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2506.14522 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909651548766208 |
|---|---|
| author | Juntarapomdach, Chaipattana Kittipassorn, Teeradej |
| author_facet | Juntarapomdach, Chaipattana Kittipassorn, Teeradej |
| contents | A transparent rectangle visibility graph (TRVG) is a graph whose vertices can be represented by a collection of non-overlapping rectangles in the plane whose sides are parallel to the axes such that two vertices are adjacent if and only if there is a horizontal or vertical line intersecting the interiors of their rectangles.
We show that every threshold graph, tree, cycle, rectangular grid graph, triangular grid graph and hexagonal grid graph is a TRVG. We also obtain a maximum number of edges of a bipartite TRVG and characterize complete bipartite TRVGs. More precisely, a bipartite TRVG with $n$ vertices has at most $2n-2$ edges. The complete bipartite graph $K_{p,q}$ is a TRVG if and only if $\min\{p,q\} \le 2$ or $(p,q) \in \{(3,3), (3,4)\}$. We prove similar results for the torus. Moreover, we study whether powers of cycles and their complements are TRVGs. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_14522 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Transparent Rectangle Visibility Graphs Juntarapomdach, Chaipattana Kittipassorn, Teeradej Combinatorics 05C62 A transparent rectangle visibility graph (TRVG) is a graph whose vertices can be represented by a collection of non-overlapping rectangles in the plane whose sides are parallel to the axes such that two vertices are adjacent if and only if there is a horizontal or vertical line intersecting the interiors of their rectangles. We show that every threshold graph, tree, cycle, rectangular grid graph, triangular grid graph and hexagonal grid graph is a TRVG. We also obtain a maximum number of edges of a bipartite TRVG and characterize complete bipartite TRVGs. More precisely, a bipartite TRVG with $n$ vertices has at most $2n-2$ edges. The complete bipartite graph $K_{p,q}$ is a TRVG if and only if $\min\{p,q\} \le 2$ or $(p,q) \in \{(3,3), (3,4)\}$. We prove similar results for the torus. Moreover, we study whether powers of cycles and their complements are TRVGs. |
| title | Transparent Rectangle Visibility Graphs |
| topic | Combinatorics 05C62 |
| url | https://arxiv.org/abs/2506.14522 |