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

DOI10.1016/J.IPL.2010.04.019zbMATH Open1233.68137OpenAlexW1988637831MaRDI QIDQ763547FDOQ763547

Mohammadreza Razzazi, Alireza Bagheri

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

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

zbMATH Keywords

computational complexitycomputational geometrypoint-set embeddinggeometric embeddingconstrained graph drawingpartial drawing

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Optimal Algorithms to Embed Trees in a Point Set
• ON EXTENDING A PARTIAL STRAIGHT-LINE DRAWING
• Embedding planar graphs at fixed vertex locations
• Bipartite embeddings of trees in the plane
• Point-set embeddings of trees with given partial drawings
• Drawing colored graphs on colored points
• On embedding an outer-planar graph in a point set
• The rooted tree embedding problem into points in the plane
• 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
• Title not available (Why is that?)

Cited In (7)

• Planar embeddability of the vertices of a graph using a fixed point set is NP-hard
• Inserting one edge into a simple drawing is hard
• Degree constrained tree embedding into points in the plane
• On L-shaped point set embeddings of trees: first non-embeddable examples
• Every set of disjoint line segments admits a binary tree
• Straight-line embeddings of two rooted trees in the plane
• Extending simple 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)