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.

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.

Item Type:	Conference Paper
Classifications:	G Algorithms and Complexity > G.280 Canonical Ordering P Styles > P.540 Planar P Styles > P.840 Upward
URI:	http://gdea.informatik.uni-koeln.de/id/eprint/1624

Actions (login required)

View Item