×

Building blocks of upward planar digraphs. (English) Zbl 1161.68676

Summary: The upward planarity testing problem consists of testing if a digraph admits a drawing such that all edges in are monotonically increasing in the vertical direction and no edges in cross. In this paper we reduce the problem of testing a digraph for upward planarity to the problem of testing if its blocks admit upward planar drawings with certain properties. We also show how to test if a block of a digraph admits an upward planar drawing with the aforementioned properties.

MSC:

68R10 Graph theory (including graph drawing) in computer science
PDFBibTeX XMLCite
Full Text: DOI EuDML EMIS