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.
Description
Planar L-Drawings of Directed Graphs | SpringerLink
%0 Conference Paper
%1 10.1007/978-3-319-73915-1_36
%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
%B Proc. 25th Int. Symp. Graph Drawing & Network Vis. (GD'17)
%C Cham
%D 2017
%E Frati, Fabrizio
%E Ma, Kwan-Liu
%I Springer International Publishing
%K conference myown publication
%P 465--478
%R 978-3-319-73915-1_36
%T Planar L-Drawings of Directed Graphs
%V 10692
%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.
%@ 978-3-319-73915-1
@inproceedings{10.1007/978-3-319-73915-1_36,
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 = {2018-01-26T14:45:54.000+0100},
address = {Cham},
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/24fece7a46a7c85439fbe3c66fa240503/chaplick},
booktitle = {Proc. 25th Int. Symp. Graph Drawing & Network Vis. (GD'17)},
description = {Planar L-Drawings of Directed Graphs | SpringerLink},
doi = {978-3-319-73915-1_36},
editor = {Frati, Fabrizio and Ma, Kwan-Liu},
interhash = {9250c60533cb1399d195b0a9f284df7f},
intrahash = {4fece7a46a7c85439fbe3c66fa240503},
isbn = {978-3-319-73915-1},
keywords = {conference myown publication},
pages = {465--478},
publisher = {Springer International Publishing},
series = {LNCS},
timestamp = {2018-01-26T14:51:55.000+0100},
title = {Planar L-Drawings of Directed Graphs},
volume = 10692,
year = 2017
}