Planar acyclic oriented graphs |
| |
Authors: | Carsten Thomassen |
| |
Affiliation: | (1) Mathematical Institute, The Technical University of Denmark, Building 303, DK-2800 Lyngby, Denmark |
| |
Abstract: | A plane Hasse representation of an acyclic oriented graph is a drawing of the graph in the Euclidean plane such that all arcs are straight-line segments directed upwards and such that no two arcs cross. We characterize completely those oriented graphs which have a plane Hasse representation such that all faces are bounded by convex polygons. From this we derive the Hasse representation analogue, due to Kelly and Rival of Fary's theorem on straight-line representations of planar graphs and the Kuratowski type theorem of Platt for acyclic oriented graphs with only one source and one sink. Finally, we describe completely those acyclic oriented graphs which have a vertex dominating all other vertices and which have no plane Hasse representation, a problem posed by Trotter. |
| |
Keywords: | 05C10 06A10 |
本文献已被 SpringerLink 等数据库收录! |
|