Minimal Embedding Dimensions of Rectangle k-Visibility Graphs

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 axis-aligned hyperrectangles in $d$-space, such that there is an axis-parallel 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.$