Improved algorithms for the point-set embeddability problem for plane 3-trees

DOI10.1142/S1793830912500097MaRDI QIDQ2905309zbMATH OpenOpenAlexFDO

Authors Tanaeem M. Moosa, M. Sohel Rahman

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

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

Recommendations

• Improved algorithms for the point-set embeddability problem for plane 3-trees
• Point-set embeddings of plane 3-trees (extended abstract)
• Point-set embeddings of plane 3-trees
• Plane 3-trees: embeddability and approximation (extended abstract)
• Plane 3-trees: embeddability and approximation

Cites work

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

Cited in

(4)

• On embedding an outer-planar graph in a point set
• Embedding plane 3-trees in \(\mathbb R^{2}\) and \(\mathbb R^{3}\)
• Optimal point-set embedding of wheel graphs and a sub-class of 3-trees
• Improved algorithms for the point-set embeddability problem for plane 3-trees

This page was built for publication: Improved algorithms for the point-set embeddability problem for plane 3-trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2905309)