2025/06/17 by Juntarapomdach, Chaipattana, Kittipassorn, Teeradej
#05C62 #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2506.14522
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 Kp,q is a TRVG if and only if min\p,q\ ≤ 2 or (p,q) ∈ \(3,3), (3,4)\. We prove similar results for the torus. Moreover, we study whether powers of cycles and their complements are TRVGs.