Zusammenfassung
In this paper, we study drawings of directed
graphs. We use the L-drawing standard where each
edge is represented by a polygonal chain that
consists of a vertical line segment incident to the
source of the edge and a horizontal line segment
incident to the target. First, we consider
planar L-drawings. We provide necessary conditions
for the existence of these drawings and show that
testing for the existence of a planar L-drawing is
an NP-complete problem. We also show how to decide
in linear time whether there exists a planar
L-drawing of a plane directed graph with a fixed
assignment of the edges to the four sides (top,
bottom, left, and right) of the vertices. \par
Second, we consider upward- (resp.\
upward-rightward-) planar L-drawings. We provide
upper bounds on the maximum number of edges of
graphs admitting such drawings. Moreover, we
characterize the directed st-graphs admitting an
upward- (resp.\ upward-rightward-) planar L-drawing
as exactly those admitting an embedding supporting a
bitonic (resp.\ monotonically decreasing)
st-ordering.
Nutzer