Planar acyclic oriented graphs (Q1825205)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 4120192
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Planar acyclic oriented graphs |
scientific article; zbMATH DE number 4120192 |
Statements
Planar acyclic oriented graphs (English)
0 references
1989
0 references
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.
0 references
Hasse diagrams
0 references
convex representation
0 references
acyclic oriented graph
0 references
0.7605707049369812
0 references
0.7586674094200134
0 references
0.7579441666603088
0 references
