The minimum-edge non-TRVG conjecture for
The minimum-edge non-TRVG conjecture for
Let a transparent rectangle visibility graph (TRVG) be a graph admitting a representation by axis-parallel rectangles in which two vertices are adjacent when their rectangles are visible to one another, and call a graph that has no such representation a non-TRVG. The complete bipartite graph has edges.
Minimum-edge non-TRVG conjecture. is a non-TRVG with the least number of edges.
The paper establishes that is a non-TRVG and reports that no non-TRVG with fewer than edges was found; the conjectured minimality remains open.
Sources & referencesView supporting material
Primary source
Chaipattana Juntarapomdach and Teeradej Kittipassorn, “Transparent Rectangle Visibility Graphs”, arXiv:2506.14522 (2025).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.