Planar L-Drawings of Directed Graphs


  • Steven Chaplick Maastricht University
  • Markus Chimani Universität Osnabrück
  • Sabine Cornelsen Universität Konstanz
  • Giordano Da Lozzo Roma Tre University
  • Martin Nöllenburg TU Wien
  • Maurizio Patrignani Roma Tre University
  • Ioannis G. Tollis University of Crete
  • Alexander Wolff Universität Würzburg



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.




How to Cite

Chaplick, S., Chimani, M., Cornelsen, S., Da Lozzo, G., Nöllenburg, M., Patrignani, M., … Wolff, A. (2023). Planar L-Drawings of Directed Graphs. Computing in Geometry and Topology, 2(1), 7:1–7:15.



Original Research Articles