Embeddings of binary trees in lines
type: Item
instance of: scholarly article
title: Embeddings of binary trees in lines
zbMATH Open document ID: 0565.68060
DOI: 10.1016/0304-3975(85)90050-7
author: Krzysztof Diks
published in: Theoretical Computer Science
publication date: 1985-01-01T00:00:00Z
review text: We show that any n-vertex binary tree can be embedded in a line with dilation-cost \(O(n/\log_ 2 n)\). A provided proof is fully constructive.
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 3902053
zbMATH Keywords: graph embedding
zbMATH Keywords: dilation cost
MaRDI profile type: Publication
full work available at URL: 0304-3975(85)90050-7
OpenAlex ID: W1995744895
cites work: On the computational power of pushdown automata
cites work: Complexity Results for Bandwidth Minimization
cites work: Q3914447
cites work: Bounds on the costs of data encodings
Recommended article: Two results on linear embeddings of complete binary trees
Recommended article: Optimal embedding of complete binary trees into lines and grids
Recommended article: Q4694714
Recommended article: Optimal distortion embedding of complete binary trees into lines
Recommended article: Straight-line embeddings of two rooted trees in the plane
Recommended article: Embedding of trees in Euclidean spaces
Recommended article: Lattice embeddings of trees
Recommended article: Bipartite embeddings of trees in the plane
Recommended article: Q3331234
Recommended article: Embedding complete binary trees into hypercubes
description: scientific article; zbMATH DE number 3902053