Some near-optimal embeddings of complete binary and ternary trees in rectangular lattices of minimum length

Recieved: 01/15/2025

Accepted: 01/31/2025

Published: 06/20/2025

Keywords: tree embedding, rectangular lattices, minimum length

To cite this article

Lozhkin S.A., Mo Di Some near-optimal embeddings of complete binary and ternary trees in rectangular lattices of minimum length. // Moscow University Journal. Series 15. Computational Mathematics and Cybernetics. 2025. N 2, p.30-37 https://doi.org/10.55959/MSU/0137–0782–15–2025–49–2–30–37.

This work is licensed under a Сreative Commons Atribiution - NonCommercial 4.0 International (CC BY-NC 4.0)

Lozhkin S.A. (Lomonosov Moscow State University (MSU))
Mo Di (Lomonosov Moscow State University (MSU))

Abstract

This paper solves the construction problem of embedding the complete rooted binary and ternary trees with k, k =1, 2, . . . , levels in rectangular lattices (RL) with minimum length and near minimum height. It is assumed that different vertices of the tree go to different (main) vertices of the RL, with the leaves of the tree going to the vertices of the RL located on its horizontal sides. It is also assumed that the edges of the tree go to simple (transit) chains of the RL, which connect the images of their end vertices and do not pass through other main vertices, with no more than 1 (correspondingly 2) transit chains passing through the same edge (the same vertex) of the RL.