Embeddings of complete binary trees into grids and extended grids with total vertex-congestion 1
type: Item
instance of: scholarly article
title: Embeddings of complete binary trees into grids and extended grids with total vertex-congestion 1
zbMATH Open document ID: 0949.05016
DOI: 10.1016/S0166-218X(99)00161-4
author: Yanyan Li
published in: Discrete Applied Mathematics
publication date: 2000-11-29T00:00:00Z
review text: 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\).
Mathematics Subject Classification ID: 05C10
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 05C05
Mathematics Subject Classification ID: 68M10
Mathematics Subject Classification ID: 68W35
zbMATH DE Number: 1395035
zbMATH Keywords: complete binary tree
zbMATH Keywords: extended grid
zbMATH Keywords: embeddings
zbMATH Keywords: total vertex-congestion
zbMATH Keywords: square grid
MaRDI profile type: Publication
cites work: Efficient Embeddings of Binary Trees in VLSI Arrays
cites work: Q4694714
cites work: EMBEDDINGS OF COMPLETE BINARY TREES INTO EXTENDED GRIDS WITH EDGE-CONGESTION 1∗
cites work: Q3477932
cites work: Q3326832
cites work: Q4028115
full work available at URL: s0166-218x(99)00161-4
OpenAlex ID: W2054681864
description: scientific article; zbMATH DE number 1395035