Upward Straight-Line Embeddings of Directed Graphs into Point Sets

DOI10.1007/978-3-540-92248-3_12zbMath1202.05052OpenAlexW1871980631MaRDI QIDQ5302049

Fabrizio Frati, Alejandro Estrella-Balderrama, Stephen G. Kobourov

Publication date: 20 January 2009

Published in: Graph-Theoretic Concepts in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-92248-3_12

zbMATH Keywords

directed graphsupward straight-line embedding

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Directed graphs (digraphs), tournaments (05C20) Graph representations (geometric and intersection representations, etc.) (05C62) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Related Items

Upward straight-line embeddings of directed graphs into point sets

Cites Work

• Unnamed Item
• Unnamed Item
• 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
• On simultaneous planar graph embeddings
• 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
• 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
• Computing Upward Topological Book Embeddings of Upward Planar Digraphs