Optimization of layout for embedding complete k-partite graphs into line graphs of certain tree architectures

The capability of one architecture to simulate another serves as the foundation for network comparison, with embedding playing a key role in analyzing these simulations. In architectural simulation, graph embedding is one of the most powerful techniques for executing parallel algorithms and modeling diverse interconnection networks. In our earlier work, we listed an open problem that the determination of wirelength for embeddings of complete multipartite graphs into line graphs of tree-based interconnection architectures, specifically k-ary trees, banana trees, and firecracker trees. In the present paper, we explicitly construct embeddings of complete k-partite graphs into the line graphs of these three architectures and derive exact wirelength expressions. Thus, this work partially resolves the open problem posed in [1]. These results contribute toward optimized VLSI layout design and efficient Network-on-Chip (NoC) architectures.