<div class="csl-bib-body">
<div class="csl-entry">Chaplick, S., Cornelsen, S., Nöllenburg, M., Tollis, I. G., Chimani, M., Da Lozzo, G., Patrignani, M., & Wolf, A. (2023). Planar L-drawings of directed graphs. <i>Computing in Geometry and Topology</i>, <i>2</i>(1), 7:1-7:15. https://doi.org/10.34726/5407</div>
</div>
-
dc.identifier.uri
http://hdl.handle.net/20.500.12708/193205
-
dc.identifier.uri
https://doi.org/10.34726/5407
-
dc.description.abstract
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.
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.
