Planar straight-line point-set embedding of trees with partial embeddings

DOI10.1016/J.IPL.2010.04.019MaRDI QIDQ763547zbMATH OpenOpenAlexFDO

Authors Alireza Bagheri, Mohammadreza Razzazi

Publication date 12 March 2012

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ipl.2010.04.019

zbMATH Keywords

computational complexitycomputational geometryconstrained graph drawinggeometric embeddingpartial drawingpoint-set embedding

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Recommendations

• Planar embedding of trees on point sets without the general position assumption
• Point-set embeddings of trees with given partial drawings
• Point-set embeddings of plane 3-trees
• Point-set embeddings of plane 3-trees (extended abstract)
• Point-Set Embedding of Trees with Edge Constraints
• Straight-line embeddings of two rooted trees in the plane
• Degree constrained tree embedding into points in the plane
• On L-shaped point set embeddings of trees: first non-embeddable examples
• On L-shaped point set embeddings of trees: first non-embeddable examples
• The rooted tree embedding problem into points in the plane

Cites work

• Bipartite embeddings of trees in the plane
• Drawing colored graphs on colored points
• Embedding planar graphs at fixed vertex locations
• Embedding Vertices at Points: Few Bends Suffice for Planar Graphs
• scientific article; zbMATH DE number 431516 (Why is no real title available?)
• scientific article; zbMATH DE number 2123123 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• On embedding an outer-planar graph in a point set
• ON EXTENDING A PARTIAL STRAIGHT-LINE DRAWING
• Optimal Algorithms to Embed Trees in a Point Set
• Planar embeddability of the vertices of a graph using a fixed point set is NP-hard
• Point-set embeddings of trees with given partial drawings
• The rooted tree embedding problem into points in the plane

Cited in

(10)

• Degree constrained tree embedding into points in the plane
• Straight-line embeddings of two rooted trees in the plane
• On L-shaped point set embeddings of trees: first non-embeddable examples
• Extending simple drawings
• Planar embeddability of the vertices of a graph using a fixed point set is NP-hard
• Planar embedding of trees on point sets without the general position assumption
• Inserting one edge into a simple drawing is hard
• Every set of disjoint line segments admits a binary tree
• A linear-time approximation algorithm for the minimum-length geometric embedding of trees
• Point-set embeddings of trees with given partial drawings

This page was built for publication: Planar straight-line point-set embedding of trees with partial embeddings

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