Planar acyclic oriented graphs
type: Item
instance of: scholarly article
title: Planar acyclic oriented graphs
zbMATH Open document ID: 0684.05021
DOI: 10.1007/BF00353654
author: Carsten Thomassen
published in: Order
publication date: 1989-01-01T00:00:00Z
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.
Mathematics Subject Classification ID: 05C20
Mathematics Subject Classification ID: 05C10
Mathematics Subject Classification ID: 06A06
zbMATH DE Number: 4120192
zbMATH Keywords: Hasse diagrams
zbMATH Keywords: convex representation
zbMATH Keywords: acyclic oriented graph
reviewed by: Jozef Širáň
MaRDI profile type: Publication
cites work: Fundamentals of planar ordered sets
cites work: Planar Lattices
cites work: Planar lattices and planar graphs
cites work: Planarity and duality of finite and infinite graphs
cites work: Q3216670
description: scientific article; zbMATH DE number 4120192