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

tree; sorting; approximation; minimum spanning tree; star; plane; fast approximation algorithms; geometric embedding problems

Mathematics Subject Classification ID

05C05: Trees

05C35: Extremal problems in graph theory

05C10: Planar graphs; geometric and topological aspects of graph theory

Related Items

Well-separated pair decomposition in linear time?, 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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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