Upward straight-line embeddings of directed graphs into point sets

DOI10.1016/j.comgeo.2009.07.002zbMath1221.05175OpenAlexW2031551728WikidataQ62042532 ScholiaQ62042532MaRDI QIDQ1037786

Fabrizio Frati, Emilio Di Giacomo, Alejandro Estrella-Balderrama, Giuseppe Liotta, Walter Didimo, Stephen G. Kobourov, Carla Binucci

Publication date: 16 November 2009

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

Full work available at URL: https://doi.org/10.1016/j.comgeo.2009.07.002

zbMATH Keywords

graph drawingpoint-set embeddingupward drawings

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Graph representations (geometric and intersection representations, etc.) (05C62)

Related Items (12)

Upward Straight-Line Embeddings of Directed Graphs into Point Sets ⋮ Upward planar embedding of an \(n\)-vertex oriented path on \(O(n^2)\) points ⋮ Reprint of: ``Upward planar embedding of an \(n\)-vertex oriented path on \(O(n^2)\) points ⋮ Upward Point Set Embeddability for Convex Point Sets Is in P ⋮ On upward point set embeddability ⋮ Colored anchored visibility representations in 2D and 3D space ⋮ Upward point set embeddings of paths and trees ⋮ Small universal point sets for \(k\)-outerplanar graphs ⋮ Computing upward topological book embeddings of upward planar digraphs ⋮ Upward Point-Set Embeddability ⋮ Upward straight-line embeddings of directed graphs into point sets ⋮ THE POINT-SET EMBEDDABILITY PROBLEM FOR PLANE GRAPHS

Cites Work

• Unnamed Item
• 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
• Upward straight-line embeddings of directed graphs into point sets
• Algorithms for plane representations of acyclic digraphs
• Area requirement and symmetry display of planar upward drawings
• On embedding an outer-planar graph in a point set
• Book embeddability of series-parallel digraphs
• Stack and Queue Layouts of Directed Acyclic Graphs: Part I
• 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
• Upward Straight-Line Embeddings of Directed Graphs into Point Sets
• Computing Upward Topological Book Embeddings of Upward Planar Digraphs

This page was built for publication: Upward straight-line embeddings of directed graphs into point sets