A Compact Layout for the Three-Dimensional Tree of Meshes

Ronald I. Greenberg; Charles E. Leiserson

doi:10.1016/0893-9659(88)90066-3

A Compact Layout for the Three-Dimensional Tree of Meshes

Ronald I. Greenberg, Charles E. Leiserson

Department of Computer Science

Research output: Contribution to journal › Article › peer-review

Abstract

We provide a simple demonstration that the n × n × n tree of meshes graph truncated to l levels can be embedded in a three-dimensional (3D) grid using volume . The maximum wire length in the embedding of the graph is . This embedding simplifies the method developed by Leighton and Rosenberg [6] for the 3D embeddings of general graphs and allows the framework of Bhatt and Leighton [1] for 2D graph layout to be extended to 3D. It also leads to good 3D layouts for various fat-tree routing networks [8,2] and the 3D meshes of trees graph [5].

Original language	American English
Journal	Computer Science: Faculty Publications and Other Works
Volume	1
Issue number	2
DOIs	https://doi.org/10.1016/0893-9659(88)90066-3
State	Published - Jan 1 1988

Keywords

tree of meshes
3D
graph layout
routing networks

Disciplines

Computer Sciences
Theory and Algorithms

Access to Document

10.1016/0893-9659(88)90066-3License: Unspecified

http://dx.doi.org/10.1016/0893-9659(88)90066-3

Cite this

@article{a6d97ecb78774350b65cc67392f67733,

title = "A Compact Layout for the Three-Dimensional Tree of Meshes",

abstract = " We provide a simple demonstration that the n × n × n tree of meshes graph truncated to l levels can be embedded in a three-dimensional (3D) grid using volume . The maximum wire length in the embedding of the graph is . This embedding simplifies the method developed by Leighton and Rosenberg [6] for the 3D embeddings of general graphs and allows the framework of Bhatt and Leighton [1] for 2D graph layout to be extended to 3D. It also leads to good 3D layouts for various fat-tree routing networks [8,2] and the 3D meshes of trees graph [5].",

keywords = "tree of meshes, 3D, graph layout, routing networks",

author = "Greenberg, {Ronald I.} and Leiserson, {Charles E.}",

note = "Applied Mathematics Letters, Volume 1, Issue 2, 1988, Pages 171–176",

year = "1988",

month = jan,

day = "1",

doi = "10.1016/0893-9659(88)90066-3",

language = "American English",

volume = "1",

journal = "Computer Science: Faculty Publications and Other Works",

number = "2",

}

TY - JOUR

T1 - A Compact Layout for the Three-Dimensional Tree of Meshes

AU - Greenberg, Ronald I.

AU - Leiserson, Charles E.

N1 - Applied Mathematics Letters, Volume 1, Issue 2, 1988, Pages 171–176

PY - 1988/1/1

Y1 - 1988/1/1

N2 - We provide a simple demonstration that the n × n × n tree of meshes graph truncated to l levels can be embedded in a three-dimensional (3D) grid using volume . The maximum wire length in the embedding of the graph is . This embedding simplifies the method developed by Leighton and Rosenberg [6] for the 3D embeddings of general graphs and allows the framework of Bhatt and Leighton [1] for 2D graph layout to be extended to 3D. It also leads to good 3D layouts for various fat-tree routing networks [8,2] and the 3D meshes of trees graph [5].

AB - We provide a simple demonstration that the n × n × n tree of meshes graph truncated to l levels can be embedded in a three-dimensional (3D) grid using volume . The maximum wire length in the embedding of the graph is . This embedding simplifies the method developed by Leighton and Rosenberg [6] for the 3D embeddings of general graphs and allows the framework of Bhatt and Leighton [1] for 2D graph layout to be extended to 3D. It also leads to good 3D layouts for various fat-tree routing networks [8,2] and the 3D meshes of trees graph [5].

KW - tree of meshes

KW - 3D

KW - graph layout

KW - routing networks

UR - https://ecommons.luc.edu/cs_facpubs/90

UR - http://dx.doi.org/10.1016/0893-9659(88)90066-3

U2 - 10.1016/0893-9659(88)90066-3

DO - 10.1016/0893-9659(88)90066-3

M3 - Article

VL - 1

JO - Computer Science: Faculty Publications and Other Works

JF - Computer Science: Faculty Publications and Other Works

IS - 2

ER -

A Compact Layout for the Three-Dimensional Tree of Meshes

Abstract

Keywords

Disciplines

Access to Document

Other files and links

Cite this