Embeddings of complete binary trees into grids and extended grids with total vertex-congestion 1 (Q1962071)

Let \(T_h\) be the complete binary tree with \(2^{h+1}-1\) vertices. The (extended) square grid \(M_r\) (\(E_r\)) has vertices \((i,j)\) for \(0 \leq i,j < r\) and two different vertices \((i,j)\) and \((k,l)\) are adjacent iff \(|i-k|+ |j-l|= 1\) (\(|i-k|\leq 1\) and \(|j-l|\leq 1\) in the extended grid). All embeddings considered have total vertex-congestion \(1\), i.e., different vertices of the guest \(T_h\) are mapped to different vertices of the host (\(M_r\) or \(E_r\)) and in case a host-vertex belongs to two paths representing different edges of the guest it is an end-vertex of both paths. If we use the well-known H-tree layout to embed \(T_{h}\) into a square grid, the expansion \(|V(M)|/ |V(T)|\) tends to \(2\) for \(h \to \infty\). The authors give recursive constructions to embed \(T_{2p}\) and \(T_{2p+1}\) into square grids with expansions approaching \(1.606\) and \(1.511\) for \(p \to \infty\). In case of extended grids the expansions approach \(1.234\) and \(1.284\).