2025/11/27 by Siraphob Buahong, Teeradej Kittipassorn, Buahong, Siraphob +7
Computer Science · Engineering · #05C62 #Advanced Graph Theory Research #Combinatorics (math.CO) #Computational Geometry and Mesh Generation #FOS: Mathematics #Structural Analysis and Optimization
paper · pdf · doi:10.48550/arxiv.2511.22660
openalex publication_date 2025/11/27 · openalex created_date 2025/12/03 · openalex updated_date 2026/07/28
We consider a graph representation in the plane, called the transparent rectangle visibility graph (TRVG), where each vertex is represented by a rectangle in the plane with sides parallel to the plane axes, in a way that any two vertices are adjacent if and only if a vertical or horizontal line can be drawn from the interior of one rectangle to the other. Expanding upon previously done work by Juntarapomdach and Kittipassorn, we show that K3,3,3 is not a TRVG, and classify complete k-partite TRVGs. We also prove that the complement of C2n is not a TRVG whenever n ≥ 15, and that every k-partite TRVG with n vertices has at most 2(k-1)n-k(k-1) edges. Furthermore, we introduce a novel representation, the intersecting transparent rectangle visibility graph (ITRVG), and show that there exists a graph that is an ITRVG but not a TRVG.