Fast geometric approximation techniques and geometric embedding problems

DOI10.1016/0304-3975(92)90252-BzbMath0776.05034MaRDI QIDQ1202926

Howard J. Karloff, Baruch Schieber, Prabhakar Raghavan, Marshall W. Bern

Publication date: 22 April 1993

Published in: Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

treesortingapproximationminimum spanning treestarplanefast approximation algorithmsgeometric embedding problems

Mathematics Subject Classification ID

Trees (05C05) Extremal problems in graph theory (05C35) Planar graphs; geometric and topological aspects of graph theory (05C10)

Related Items (4)

Two results on linear embeddings of complete binary trees ⋮ Optimal point-set embedding of wheel graphs and a sub-class of 3-trees ⋮ Combinatorial theorems about embedding trees on the real line ⋮ Well-separated pair decomposition in linear time?

Cites Work

• Graphs whose every transitive orientation contains almost every relation
• On optimal linear arrangements of trees
• Upper bounds for sorting integers on random access machines
• Sorting helps for Voronoi diagrams
• Approximate minimum weight matching on points in k-dimensional space
• Wafer-Scale Integration of Systolic Arrays
• Minimum Spanning Trees in k-Dimensional Space
• Approximation algorithms for convex hulls
• The complexity of restricted spanning tree problems
• Design and implementation of an efficient priority queue
• Fibonacci heaps and their uses in improved network optimization algorithms
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Fast geometric approximation techniques and geometric embedding problems