Constrained point-set embeddability of planar graphs

DOI10.1142/S021819591000344XMaRDI QIDQ3063657zbMATH OpenOpenAlexWikidataFDO

Authors Emilio Di Giacomo, Walter Didimo, Giuseppe Liotta, Henk Meijer, S. Wismath

Publication date 15 December 2010

Published in International Journal of Computational Geometry & Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1142/s021819591000344x

zbMATH Keywords

graph drawingpoint-set embeddingcurve complexityconstrained point-set embedding

Mathematics Subject Classification ID

Complexity and performance of numerical algorithms (65Y20) Numerical aspects of computer graphics, image analysis, and computational geometry (65D18)

Recommendations

• Constrained Point-Set Embeddability of Planar Graphs
• Point-Set Embedding of Trees with Edge Constraints
• Curve-constrained drawings of planar graphs
• Drawing planar graphs on a curve.
• On the hardness of point-set embeddability (extended abstract)

Cites work

• A Visibility Representation for Graphs in Three Dimensions
• Curve-constrained drawings of planar graphs
• Drawing colored graphs on colored points
• Drawing colored graphs with constrained vertex positions and few bends per edge
• Embedding Vertices at Points: Few Bends Suffice for Planar Graphs
• Embedding planar graphs at fixed vertex locations
• How to draw a planar graph on a grid
• ON EMBEDDING A GRAPH ON TWO SETS OF POINTS
• On embedding an outer-planar graph in a point set
• On the thickness of graphs of given degree
• Point-set embeddings of trees with given partial drawings
• SEMI-BALANCED PARTITIONS OF TWO SETS OF POINTS AND EMBEDDINGS OF ROOTED FORESTS
• Straight line embeddings of rooted star forests in the plane
• The rooted tree embedding problem into points in the plane

Cited in

(23)

• Plane graphs with parity constraints
• Embedding Vertices at Points: Few Bends Suffice for Planar Graphs
• Drawing graphs with vertices at specified positions and crossings at large angles
• Constrained independence system and triangulations of planar point sets
• 2-colored point-set embeddings of partial 2-trees
• Drawing planar graphs on a curve.
• Bounded Embeddings of Graphs in the Plane
• On point set embeddings for k-planar graphs with few bends per edge
• 2-colored point-set embeddings of partial 2-trees
• Embedding plane 3-trees in \(\mathbb R^{2}\) and \(\mathbb R^{3}\)
• Point set embedding in 3D
• Point-Set Embedding of Trees with Edge Constraints
• k-colored Point-set Embeddability of Outerplanar Graphs
• Drawing planar graphs on points inside a polygon
• Constrained Point-Set Embeddability of Planar Graphs
• Kinetic and Stationary Point-Set Embeddability for Plane Graphs
• The point-set embeddability problem for plane graphs
• Curve-constrained drawings of planar graphs
• EMBEDDING POINT SETS INTO PLANE GRAPHS OF SMALL DILATION
• Graphs embedded in the plane with a bounded number of accumulation points
• Manhattan-geodesic embedding of planar graphs
• Planar Graphs with Topological Constraints
• Plane Graphs with Parity Constraints

This page was built for publication: Constrained point-set embeddability of planar graphs

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