Plane 3-trees: embeddability and approximation

DOI10.1137/140964710MaRDI QIDQ5251619zbMATH OpenOpenAlexFDO

Authors Stephane Durocher, Debajyoti Mondal

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 drawingplane 3-treepoint-set embedding

Mathematics Subject Classification ID

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

Recommendations

• Plane 3-trees: embeddability and approximation (extended abstract)
• 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
• Embedding plane 3-trees in \(\mathbb R^{2}\) and \(\mathbb R^{3}\)

Cites work

• A 1.235 lower bound on the number of points needed to draw alln-vertex planar graphs
• A decomposition theorem for partially ordered sets
• Curve-constrained drawings of planar graphs
• Embedding planar graphs at fixed vertex locations
• Embedding plane 3-trees in \(\mathbb R^{2}\) and \(\mathbb R^{3}\)
• Embedding Vertices at Points: Few Bends Suffice for Planar Graphs
• Graph Drawing
• How to draw a planar graph on a grid
• scientific article; zbMATH DE number 432759 (Why is no real title available?)
• Illumination by floodlights
• Improved algorithms for the point-set embeddability problem for plane 3-trees
• Maintenance of configurations in the plane
• Manhattan-geodesic embedding of planar graphs
• On embedding an outer-planar graph in a point set
• On point-sets that support planar graphs
• On simultaneous planar graph embeddings
• On the hardness of point-set embeddability (extended abstract)
• 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
• Plane 3-trees: embeddability and approximation (extended abstract)
• Point-set embeddings of plane 3-trees
• Quasi-optimal upper bounds for simplex range searching and new zone theorems
• The Hamiltonian Augmentation Problem and Its Applications to Graph Drawing
• The point-set embeddability problem for plane graphs
• The rooted tree embedding problem into points in the plane
• Universal sets of \(n\) points for one-bend drawings of planar graphs with \(n\) vertices

Cited in

(8)

• Plane 3-trees: embeddability and approximation (extended abstract)
• Improved algorithms for the point-set embeddability problem for plane 3-trees
• Point-set embeddings of plane 3-trees (extended abstract)
• Improved algorithms for the point-set embeddability problem for plane 3-trees
• The Planar Slope Number of Planar Partial 3-Trees of Bounded Degree
• Point-set embeddings of plane 3-trees
• The number of connected sets in Apollonian networks
• Clustering analysis of a dissimilarity: a review of algebraic and geometric representation

This page was built for publication: Plane 3-trees: embeddability and approximation

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