@article{Chaplick_Chimani_Cornelsen_Da Lozzo_Nöllenburg_Patrignani_Tollis_Wolff_2023, title={Planar L-Drawings of Directed Graphs}, volume={2}, url={https://www.cgt-journal.org/index.php/cgt/article/view/43}, DOI={10.57717/cgt.v2i1.43}, abstractNote={<div class="page" title="Page 1"> <div class="layoutArea"> <div class="column"> <p>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.</p> <p>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.</p> <p>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.</p> </div> </div> </div>}, number={1}, journal={Computing in Geometry and Topology}, author={Chaplick, Steven and Chimani, Markus and Cornelsen, Sabine and Da Lozzo, Giordano and Nöllenburg, Martin and Patrignani, Maurizio and Tollis, Ioannis G. and Wolff, Alexander}, year={2023}, month={Nov.}, pages={7:1–7:15} }