Upward planarity testing (Q1904391)
From MaRDI portal
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Upward planarity testing |
scientific article |
Statements
Upward planarity testing (English)
0 references
11 April 1996
0 references
A digraph is said to be upward planar if it has a planar drawing with the edges monotonically increasing in the vertical direction. This survey paper overviews the literature on upward planarity testing. Several characterizations are presented of upward planarity; upward planarity testing algorithms are described for special classes of digraphs, and a proof is sketched for NP-completeness of upward planarity testing.
0 references
planar drawing
0 references
upward planarity testing
0 references
digraphs
0 references
NP-completeness
0 references
0 references
