Optimal point-set embedding of wheel graphs and a sub-class of 3-trees

DOI10.1007/S13160-016-0232-XMaRDI QIDQ2396907zbMATH OpenOpenAlexFDO

Authors Majid Hosseinzadegan, Alireza Bagheri

Publication date 29 May 2017

Published in Japan Journal of Industrial and Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s13160-016-0232-x

zbMATH Keywords

NP-completenesswheel graphgraph drawingpoint-set embedding3-tree

Mathematics Subject Classification ID

Trees (05C05) Graph algorithms (graph-theoretic aspects) (05C85) 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) Graph representations (geometric and intersection representations, etc.) (05C62)

Recommendations

• Point-set embeddings of plane 3-trees
• Point-set embeddings of plane 3-trees (extended abstract)
• Improved algorithms for the point-set embeddability problem for plane 3-trees
• Improved algorithms for the point-set embeddability problem for plane 3-trees
• Optimal Algorithms to Embed Trees in a Point Set
• Point-Set Embedding of Trees with Edge Constraints
• On embedding triconnected cubic graphs on point sets
• Point-set embeddings of trees with given partial drawings
• The point-set embeddability problem for plane graphs
• The point-set embeddability problem for plane graphs

Cites work

• scientific article; zbMATH DE number 1693468 (Why is no real title available?)
• scientific article; zbMATH DE number 1424307 (Why is no real title available?)
• scientific article; zbMATH DE number 3346402 (Why is no real title available?)
• scientific article; zbMATH DE number 3047038 (Why is no real title available?)
• A linear-time algorithm for drawing a planar graph on a grid
• Computational geometry. Algorithms and applications.
• Convex Maps
• Embedding Vertices at Points: Few Bends Suffice for Planar Graphs
• Embedding planar graphs at fixed vertex locations
• Fast geometric approximation techniques and geometric embedding problems
• Manhattan-geodesic embedding of planar graphs
• Minimum height path partitioning of trees
• Minimum-area drawings of plane 3-trees
• On embedding an outer-planar graph in a point set
• On simple polygonalizations with optimal area
• 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 plane 3-trees
• Point-set embeddings of trees with given partial drawings
• The point-set embeddability problem for plane graphs
• The rooted tree embedding problem into points in the plane

Cited in

(1)

• A linear-time approximation algorithm for the minimum-length geometric embedding of trees

This page was built for publication: Optimal point-set embedding of wheel graphs and a sub-class of 3-trees

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