Point-set embeddings of plane \(3\)-trees

DOI10.1016/j.comgeo.2011.09.002zbMath1244.65032OpenAlexW2063911255WikidataQ60608614 ScholiaQ60608614MaRDI QIDQ427050

Md. Saidur Rahman, Debajyoti Mondal, Rahnuma Islam Nishat

Publication date: 13 June 2012

Published in: Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.comgeo.2011.09.002

zbMATH Keywords

algorithmdynamic programminglower boundNP-completegraphical examplesplane \(3\)-treepoint-set embedding

Mathematics Subject Classification ID

Dynamic programming (90C39) Numerical aspects of computer graphics, image analysis, and computational geometry (65D18)

Related Items

IMPROVED ALGORITHMS FOR THE POINT-SET EMBEDDABILITY PROBLEM FOR PLANE 3-TREES, Optimal point-set embedding of wheel graphs and a sub-class of 3-trees, Universal point sets for planar three-trees, Plane 3-Trees: Embeddability and Approximation, THE POINT-SET EMBEDDABILITY PROBLEM FOR PLANE GRAPHS

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• How to draw a planar graph on a grid
• The rooted tree embedding problem into points in the plane
• On embedding an outer-planar graph in a point set
• Point-Set Embeddings of Plane 3-Trees
• Improved Algorithms for the Point-Set Embeddability Problem for Plane 3-Trees
• Minimum-Area Drawings of Plane 3-Trees
• Embedding Plane 3-Trees in ℝ2 and ℝ3
• On embedding triconnected cubic graphs on point sets
• Embedding Vertices at Points: Few Bends Suffice for Planar Graphs
• Planar embeddability of the vertices of a graph using a fixed point set is NP-hard
• Embedding planar graphs at fixed vertex locations