Planar L-Drawings of Directed Graphs.Chaplick, Steven and Chimani, Markus and Cornelsen, Sabine and Da Lozzo, Giordano and Nöllenburg, Martin and Patrignani, Maurizio and Tollis, Ioannis G. and Wolff, Alexander (2017) Planar L-Drawings of Directed Graphs. In: Graph Drawing and Network Visualization. GD 2017, September 25-27 , pp. 465-478(Official URL: https://doi.org/10.1007/978-3-319-73915-1_36). Full text not available from this repository.
Official URL: https://doi.org/10.1007/978-3-319-73915-1_36
AbstractWe 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.
Actions (login required)
|