%0 Journal Article %1 cccdnptw-plddg-JGAA23 %A Chaplick, Steven %A Chimani, Markus %A Cornelsen, Sabine %A Da Lozzo, Giordano %A Nöllenburg, Martin %A Patrignani, Maurizio %A Tollis, Ioannis G. %A Wolff, Alexander %D 2023 %J Computing in Geometry and Topology %K %N 1 %P 7:1--7:15 %R 10.57717/cgt.v2i1.43 %T Planar L-Drawings of Directed Graphs %V 2 %X 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.

@article{cccdnptw-plddg-JGAA23, 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. \par 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.}, added-at = {2023-12-28T10:36:54.000+0100}, author = {Chaplick, Steven and Chimani, Markus and Cornelsen, Sabine and {Da Lozzo}, Giordano and N{\"o}llenburg, Martin and Patrignani, Maurizio and Tollis, Ioannis G. and Wolff, Alexander}, biburl = {https://www.bibsonomy.org/bibtex/2bf042134f1d469812b6ea192dce1ec8d/awolff}, doi = {10.57717/cgt.v2i1.43}, interhash = {07d0cf520c2fe67736a07cbcd8c66fb6}, intrahash = {bf042134f1d469812b6ea192dce1ec8d}, journal = {Computing in Geometry and Topology}, keywords = {}, number = 1, pages = {7:1--7:15}, timestamp = {2023-12-28T10:36:54.000+0100}, title = {Planar L-Drawings of Directed Graphs}, volume = 2, year = 2023 }