On embedding an outer-planar graph in a point set

DOI10.1016/S0925-7721(01)00069-4zbMath1012.05057MaRDI QIDQ1862133

Prosenjit Bose

Publication date: 10 March 2003

Published in: Computational Geometry (Search for Journal in Brave)

zbMATH Keywords

graph drawinggraph embeddingstraight-line embedding

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

On triconnected and cubic plane graphs on given point sets ⋮ IMPROVED ALGORITHMS FOR THE POINT-SET EMBEDDABILITY PROBLEM FOR PLANE 3-TREES ⋮ Upward Straight-Line Embeddings of Directed Graphs into Point Sets ⋮ Plane Graphs with Parity Constraints ⋮ On simultaneous planar graph embeddings ⋮ Orthogeodesic point-set embedding of trees ⋮ Optimal point-set embedding of wheel graphs and a sub-class of 3-trees ⋮ Embedding Plane 3-Trees in ℝ2 and ℝ3 ⋮ Orthogeodesic Point-Set Embedding of Trees ⋮ On Point-Sets That Support Planar Graphs ⋮ Small Point Sets for Simply-Nested Planar Graphs ⋮ Upward Point Set Embeddability for Convex Point Sets Is in P ⋮ On embedding triconnected cubic graphs on point sets ⋮ Drawing Planar Graphs with Many Collinear Vertices ⋮ The dual diameter of triangulations ⋮ Point-set embeddings of plane \(3\)-trees ⋮ On upward point set embeddability ⋮ Plane graphs with parity constraints ⋮ Point-set embeddings of trees with given partial drawings ⋮ Improved Bounds for Drawing Trees on Fixed Points with L-Shaped Edges ⋮ Computing Upward Topological Book Embeddings of Upward Planar Digraphs ⋮ Upward point set embeddings of paths and trees ⋮ -shaped point set embeddings of high-degree plane graphs ⋮ Small universal point sets for \(k\)-outerplanar graphs ⋮ Simultaneous graph embedding with bends and circular arcs ⋮ Computing upward topological book embeddings of upward planar digraphs ⋮ Universal point sets for planar three-trees ⋮ Colored simultaneous geometric embeddings and universal pointsets ⋮ Curve-constrained drawings of planar graphs ⋮ Every collinear set in a planar graph is free ⋮ CONSTRAINED POINT-SET EMBEDDABILITY OF PLANAR GRAPHS ⋮ Constrained Point-Set Embeddability of Planar Graphs ⋮ Upward Point-Set Embeddability ⋮ SEFE without Mapping via Large Induced Outerplane Graphs in Plane Graphs ⋮ Planar straight-line point-set embedding of trees with partial embeddings ⋮ Geometry and Generation of a New Graph Planarity Game ⋮ Upward straight-line embeddings of directed graphs into point sets ⋮ Plane 3-Trees: Embeddability and Approximation ⋮ Constrained Point Set Embedding of a Balanced Binary Tree ⋮ Capacitated domination: problem complexity and approximation algorithms ⋮ THE POINT-SET EMBEDDABILITY PROBLEM FOR PLANE GRAPHS

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Area requirement of visibility representations of trees
• Maintenance of configurations in the plane
• Applications of a semi-dynamic convex hull algorithm
• The rooted tree embedding problem into points in the plane
• Algorithms for drawing graphs: An annotated bibliography
• Linear area upward drawings of AVL trees
• Characterizing proximity trees
• On the convex layers of a planar set
• Optimal Algorithms to Embed Trees in a Point Set