Transparent Rectangle Visibility Graphs

Chaipattana Juntarapomdach, Teeradej Kittipassorn · 2025

Read Transparent Rectangle Visibility Graphs by Chaipattana Juntarapomdach, Teeradej Kittipassorn (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2506-14522.txt.

Introduction

Chaipattana Juntarapomdach and Teeradej Kittipassorn study a class of graphs drawn with rectangles, in a 2025 paper. Each graph point is a rectangle with sides aligned to a grid. Two points are linked when a straight flat or upright line crosses both rectangles. The rectangles may be crossed by the line, so the authors call the graphs transparent.

The authors show many known graph types fit this scheme. Trees, cycles, and several grid graphs all qualify. They also cap the number of links for graphs split into two sides. Only a few complete two-sided graphs qualify, and they list exactly which ones. Like results hold for graphs drawn on a donut shape. The paper also tests powers of cycles and their mirror graphs for the same property.

Catalog record

CREATORChaipattana Juntarapomdach, Teeradej Kittipassorn
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE25 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2506-14522

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Transparent Rectangle Visibility Graphs Chaipattana Juntarapomdach, Teeradej Kittipassorn Abstract 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 n vertices has at most 2 ​ n − 2 2n-2 edges. The complete bipartite graph K p , q K_{p,q} is a TRVG if and only if min ⁡ { p , q } ≤ 2 \min\{p,q\}\leq 2 or ( p , q ) ∈ { ( 3 , 3 ) , ( 3 , 4 ) } (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. 1 Introduction Consider a collection of non-overlapping rectangles in the plane where the sides are parallel to the axes. Two rectangles A and B see each other if there is a horizontal or vertical line segment intersecting the interiors of A and B such that it passes through no other rectangles. This naturally induces a graph whose vertices are the rectangles and two vertices are adjacent if their rectangles see each other. We call a graph which can be constructed in this way, a rectangle visibility graph , or RVG . The first problem that arises is: which graphs are RVGs? The study of RVGs was initiated in 1976 by Garey, Johnson and So [ 9 ] as a tool for designing printed circuit boards. They considered only 1\times 1 squares in the plane whose vertices are lattice points. In 1995, Dean and Hutchinson [ 4 ] discovered that a complete bipartite graph K_{p,q} where p\leq q is an RVG if and only if p\leq 4 , and moreover, every bipartite RVG with n vertices has at most 4n-12 edges. A few years later, in 1999, Hutchinson, Shermer, and Vince [ 11 ] proved that every RVG with n vertices has at most 6n-20 edges, and this bound is best possible for n\geq 8 . In 1996, Bose, Dean, Hutchinson and Shermer [ 1 ] found new classes of RVGs including graphs with maximum degree four and graphs that can be decomposed into two caterpillar forests. Recently, in 2022, Caughman, Dunn, Laison, Neudauer, Starr [ 3 ] studied the area, perimeter, height and width of the bounding box of an RVG. Many variations of RVG have been investigated including bar visibility graphs [ 7 ] , 3 -dimensional box visibility graphs [ 2 , 5 , 8 , 10 ] and polygon visibility graphs [ 6 , 13 ] . In this paper, we consider what happens if rectangles A and B still see each other even when there are other rectangles blocking the line of sight. That is, we suppose that every rectangle is transparent. Then we call such a transparent rectangle visibility graph , or TRVG . Figure 1 illustrates an example of a collection of rectangles representing different graphs as a TRVG and an RVG. TRVG RVG Figure 1 : A difference between a TRVG and an RVG Note that every induced subgraph of a TRVG is also a TRVG by deleting all rectangles corresponding to the vertices outside the induced subgraph. Our first main result proves that some classes of graphs are TRVGs. Theorem 1 . The following graphs are TRVGs: (i) a threshold graph, (ii) a tree, (iii) a cycle, (iv) an infinite rectangular grid graph, (v) an infinite triangular grid graph and (vi) an infinite hexagonal grid graph. The following two main results for bipartite TRVGs are analogous to those of Dean and Hutchinson [ 4 ] for bipartite RVGs. Consequently, we discover some bipartite non-TRVGs. Theorem 2 . Every bipartite TRVG on n vertices has at most 2n-2 edges. Moreover, this is best possible for n\geq 7 . Applying Theorem 2 , we can classify complete bipartite graphs. Theorem 3 . For p\leq q , K_{p,q} is a TRVG if and only if p\leq 2 or (p,q)\in\{(3,3),(3,4)\} . We see that K_{4,4} and K_{3,5} are non-TRVGs with respect to the plane. However, they are TRVG with respect to the torus. The same ideas of the proofs of Theorems 2 and 3 can be applied to the case of the torus. Theorem 4 . Every bipartite TRVG with respect to the torus on n vertices has at most 2n edges. Moreover, this is best possible for n\geq 8 . Theorem 5 . For p\leq q , K_{p,q} is a TRVG with respect to the torus if and only if p\leq 2 or (p,q)\in\{(3,3),(3,4),(3,5),(3,6),(4,4)\} . Furthermore, we consider a special case of regular graphs. Vertices v_{1},\dots,v_{n} form a cycle C_{n} if v_{i} and v_{j} are adjacent when |i-j|\equiv 1\pmod{n} . Generalizing this, they form the a^{th} power of C_{n} if v_{i} and v_{j} are adjacent when |i-j|\equiv k\pmod{n} for some k\leq a . We denote this graph by C^{a}_{n} and its complement by D^{a}_{n} Theorem 6 . (i) Every power of a cycle is a TRVG. (ii) D^{1}_{n} is a TRVG. (iii) D^{a}_{n} with n\geq 2a+8 is a non-TRVG when a\geq 3 . (iv) D^{a}_{n} with n\leq 2a+4 is a TRVG when a\geq 2 . Let us introduce a definition that will be used throughout this paper. Given a collection of rectangles in the plane representing a graph G and a subset of vertices U\subseteq V(G) , a bounding box of U is a box which covers all rectangles representing U and intersects no other rectangles. This paper is organized as follows. Sections 2 , 3 and 4 focus on the proof of Theorem 1 . In Section 5 , we study bipartite graphs and prove Theorems 2 , 3 , 4 and 5 . We prove Theorem 6 regarding powers of cycles in Section 6 . Finally, we leave some open problems in Section 7 . 2 Threshold Graph In this section, we will prove Theorem 1 (i) , i.e. every threshold graph is a TRVG. As one of the fundamental classes of graphs, threshold graphs have been defined in many ways (see [ 12 ] ). A graph G is a threshold graph if we can assign a real number r_{v} to each vertex v and there is a real number \theta such that for any vertex subset U of G , \sum_{v\in U}r_{v}\leq\theta if and only if U is independent in G . Equivalently, it is a graph that can be constructed by repeating these two operations: • Add an isolated vertex to the graph. • Add a universal vertex to the graph, i.e. a vertex connected to all others. Proof of Theorem 1 (i) . We will proceed by induction on the number of vertices. Clearly, a one-vertex graph is a TRVG. For the inductive step, let G be a threshold graph and let

Read the complete text