Plane 3-Trees: Embeddability and Approximation

DOI10.1137/140964710zbMath1311.05039OpenAlexW2024291353MaRDI QIDQ5251619

Debajyoti Mondal, Stephane Durocher

Publication date: 20 May 2015

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/140964710

zbMATH Keywords

approximationgraph drawingpoint-set embeddingplane 3-tree

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Planar graphs; geometric and topological aspects of graph theory (05C10) Graph representations (geometric and intersection representations, etc.) (05C62)

Related Items

Clustering analysis of a dissimilarity: a review of algebraic and geometric representation

Cites Work

• Unnamed Item
• Point-set embeddings of plane \(3\)-trees
• Curve-constrained drawings of planar graphs
• On point-sets that support planar graphs
• How to draw a planar graph on a grid
• A 1.235 lower bound on the number of points needed to draw alln-vertex planar graphs
• Universal sets of \(n\) points for one-bend drawings of planar graphs with \(n\) vertices
• On simultaneous planar graph embeddings
• Maintenance of configurations in the plane
• Quasi-optimal upper bounds for simplex range searching and new zone theorems
• The rooted tree embedding problem into points in the plane
• Illumination by floodlights
• On embedding an outer-planar graph in a point set
• Embedding stacked polytopes on a polynomial-size grid
• A decomposition theorem for partially ordered sets
• Plane 3-trees: Embeddability and Approximation
• The point-set embeddability problem for plane graphs
• On the Hardness of Point-Set Embeddability
• Improved Algorithms for the Point-Set Embeddability Problem for Plane 3-Trees
• Embedding Plane 3-Trees in ℝ2 and ℝ3
• The Hamiltonian Augmentation Problem and Its Applications to Graph Drawing
• Manhattan-Geodesic Embedding of Planar Graphs
• Optimal Algorithms to Embed Trees in a Point Set
• 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
• Graph Drawing
• Embedding planar graphs at fixed vertex locations