IMPROVED ALGORITHMS FOR THE POINT-SET EMBEDDABILITY PROBLEM FOR PLANE 3-TREES

DOI10.1142/S1793830912500097zbMath1247.05070OpenAlexW2569680952MaRDI QIDQ2905309

M. Sohel Rahman, Tanaeem M. Moosa

Publication date: 27 August 2012

Published in: Discrete Mathematics, Algorithms and Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1142/s1793830912500097

zbMATH Keywords

algorithmsplane graphpoint-setembeddability problemplane 3-treestriangular range search

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Trees (05C05) Planar graphs; geometric and topological aspects of graph theory (05C10) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (1)

Embedding Plane 3-Trees in ℝ2 and ℝ3

Cites Work

• Point-set embeddings of plane \(3\)-trees
• Quasi-optimal upper bounds for simplex range searching and new zone theorems
• The rooted tree embedding problem into points in the plane
• On embedding an outer-planar graph in a point set
• Straight line embeddings of rooted star forests in the plane
• Lower bounds for off-line range searching
• On embedding triconnected cubic graphs on point sets
• Drawing Colored Graphs on Colored Points
• Point retrieval for polygons
• Planar embeddability of the vertices of a graph using a fixed point set is NP-hard
• k-colored Point-set Embeddability of Outerplanar Graphs
• ON EMBEDDING A GRAPH ON TWO SETS OF POINTS
• SEMI-BALANCED PARTITIONS OF TWO SETS OF POINTS AND EMBEDDINGS OF ROOTED FORESTS
• Embedding planar graphs at fixed vertex locations

This page was built for publication: IMPROVED ALGORITHMS FOR THE POINT-SET EMBEDDABILITY PROBLEM FOR PLANE 3-TREES