Home  Issues  About JGAA  Instructions for Authors 
DOI: 10.7155/jgaa.00550
Minimal Embedding Dimensions of Rectangle kVisibility Graphs
Vol. 25, no. 1, pp. 5996, 2021. Regular paper.
Abstract Bar visibility graphs were adopted in the 1980s as a model to represent traces, e.g., on circuit boards and in VLSI chip designs. Two generalizations of bar visibility graphs, rectangle visibility graphs and bar $k$visibility graphs, were subsequently introduced.
Here, we combine bar $k$ and rectangle visibility graphs to form rectangle $k$visibility graphs (R$k$VGs), and further generalize these to higher dimensions. A graph is a $d$dimensional R$k$VG if and only if it can be represented with vertices as disjoint axisaligned hyperrectangles in $d$space, such that there is an axisparallel line of sight between two hyperrectangles that intersects at most $k$ other hyperrectangles if and only if there is an edge between the two corresponding vertices.
For any graph $G$ and a fixed $k$, we prove that given enough spatial dimensions, $G$ has a rectangle $k$visibility representation, and thus we define the minimal embedding dimension (MED) with $k$visibility of $G$ to be the smallest $d$ such that $G$ is a $d$dimensional R$k$VG. We study the properties of MEDs and find upper bounds on the MEDs of various types of graphs. In particular, we find that the $k$visibility MED of the complete graph on $m$ vertices $K_m$ is at most $\lceil{m/(2(k+1))}\rceil,$ of complete $r$partite graphs is at most $r+1,$ and of the $m^{\rm th}$ hypercube graph $Q_m$ is at most $\lceil{2m/3}\rceil$ in general, and at most $\lfloor{\sqrt{m}\,}\rceil$ for $k=0,~ m \ne 2.$
This work is licensed under the terms of the CCBY license.

Submitted: August 2019.
Reviewed: May 2020.
Revised: September 2020.
Reviewed: December 2020.
Revised: December 2020.
Accepted: January 2021.
Final: January 2021.
Published: January 2021.
Communicated by
Henk Meijer

Journal Supporters
