Planar acyclic oriented graphs

DOI10.1007/BF00353654MaRDI QIDQ1825205zbMATH OpenFDO

Authors Carsten Thomassen

Publication date 1989

Published in Order (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/BF00353654

zbMATH Keywords

acyclic oriented graphconvex representationHasse diagrams

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Directed graphs (digraphs), tournaments (05C20) Partial orders, general (06A06)

Review text

A plane Hasse representation of an acyclic oriented graph is a plane drawing of the graph such that the arcs are straight line segments directed upwards, no two of which cross. The author characterizes those oriented graphs which have a plane Hasse representation such that all faces are bounded by convex polygons. As a consequence, the known analog of Fáry's theorem (due to Kelly and Rival) and Platt's theorem for graphs with only one source and one sink are derived. Finally, the author describes all those acyclic oriented graphs which have a vertex dominating all other vertices but no plane Hasse representation.

Recommendations

• scientific article; zbMATH DE number 4062623
• Every triangle-free planar graph has a planar upward drawing
• Fundamentals of planar ordered sets
• Algorithms for plane representations of acyclic digraphs
• scientific article; zbMATH DE number 3882450

Cites work

• Fundamentals of planar ordered sets
• scientific article; zbMATH DE number 3882450 (Why is no real title available?)
• Planar Lattices
• Planar lattices and planar graphs
• Planarity and duality of finite and infinite graphs

Cited in

(10)

• Area requirement and symmetry display of planar upward drawings
• A note on optimal area algorithms for upward drawings of binary trees
• Upward planarity testing
• On the sphericity testing of single source digraphs
• Upward planar graphs and their duals
• Classification of planar upward embedding
• How to draw a series-parallel digraph
• Acyclic Orientation of Drawings
• Planar hypohamiltonian oriented graphs
• Upward drawings of triconnected digraphs.

This page was built for publication: Planar acyclic oriented graphs

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