Planar L-Drawings of Directed Graphs

We study planar drawings of directed graphs in the l-drawing standard. 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. Motivated by this result, we focus on upward-planar l-drawings. We show that directed st-graphs admitting an upward- (resp. Upward-rightward-) planar l-drawing are exactly those admitting a bitonic (resp. Monotonically increasing) st-ordering. We give a linear-time algorithm that computes a bitonic (resp. Monotonically increasing) st-ordering of a planar st-graph or reports that there exists none.keywordskandinsky modelvirtual edgevariable embedding settingpertinent graphdirected planar graphthese keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves