%0 Journal Article %1 journals/corr/abs-1708-09107 %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 2017 %J CoRR %K arxiv myown %T Planar L-Drawings of Directed Graphs %U http://arxiv.org/abs/1708.09107 %V abs/1708.09107 %X 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.

@article{journals/corr/abs-1708-09107, abstract = {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.}, added-at = {2019-01-17T16:48:08.000+0100}, archiveprefix = {arXiv}, 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}, bibsource = {dblp computer science bibliography, https://dblp.org}, biburl = {https://www.bibsonomy.org/bibtex/2bab8292ae046a97ac739d7fae409df9d/chaplick}, eprint = {1708.09107}, interhash = {e6a69aa59580f137b84fbc5eb86004a0}, intrahash = {bab8292ae046a97ac739d7fae409df9d}, journal = {CoRR}, keywords = {arxiv myown}, timestamp = {2019-01-17T16:48:08.000+0100}, title = {Planar L-Drawings of Directed Graphs}, url = {http://arxiv.org/abs/1708.09107}, volume = {abs/1708.09107}, year = 2017 }