Geodesic
Generalized Layerings for Arbitrary and Fixed Drawing Areas
Journal of Graph Algorithms and Applications, Special issue on Selected papers from the Twenty-fourth International Symposium on Graph Drawing and Network Visualization, GD 2016 , Tome 21 (2017) no. 5, pp. 823-856.

Voir la notice de l'article provenant de la source Journal of Graph Algorythms and Applications website

The Directed Layering Problem (DLP) solves a step of the widely used layer-based approach to automatically draw directed acyclic graphs. To cater for cyclic graphs, usually a preprocessing step is used that solves the Feedback Arc Set Problem (FASP) to make the graph acyclic before a layering is determined. Here we present the Generalized Layering Problem (GLP), which solves the combination of DLP and FASP simultaneously, allowing general graphs as input. We present an integer programming model and a heuristic to solve the NP-complete GLP and perform thorough evaluations on different sets of graphs and with different implementations for the steps of the layer-based approach. We observe that GLP reduces the number of dummy nodes significantly, can produce more compact drawings, and improves on graphs where DLP yields poor aspect ratios. The drawings resulting from GLP also turn out to be more suitable for making the best possible use of a given drawing area. However, we show that a specialized variant of GLP can yield considerable improvements w.r.t. this particular optimization goal. 
@article{JGAA_2017_21_5_a2,
     author = {Ulf R\"uegg and Thorsten Ehlers and Miro Sp\"onemann and Reinhard von Hanxleden},
     title = {Generalized {Layerings} for {Arbitrary} and {Fixed} {Drawing} {Areas}},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {823--856},
     publisher = {mathdoc},
     volume = {21},
     number = {5},
     year = {2017},
     doi = {10.7155/jgaa.00441},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00441/}
}
TY  - JOUR
AU  - Ulf Rüegg
AU  - Thorsten Ehlers
AU  - Miro Spönemann
AU  - Reinhard von Hanxleden
TI  - Generalized Layerings for Arbitrary and Fixed Drawing Areas
JO  - Journal of Graph Algorithms and Applications
PY  - 2017
SP  - 823
EP  - 856
VL  - 21
IS  - 5
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00441/
DO  - 10.7155/jgaa.00441
LA  - en
ID  - JGAA_2017_21_5_a2
ER  - 
%0 Journal Article
%A Ulf Rüegg
%A Thorsten Ehlers
%A Miro Spönemann
%A Reinhard von Hanxleden
%T Generalized Layerings for Arbitrary and Fixed Drawing Areas
%J Journal of Graph Algorithms and Applications
%D 2017
%P 823-856
%V 21
%N 5
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00441/
%R 10.7155/jgaa.00441
%G en
%F JGAA_2017_21_5_a2
Ulf Rüegg; Thorsten Ehlers; Miro Spönemann; Reinhard von Hanxleden. Generalized Layerings for Arbitrary and Fixed Drawing Areas. Journal of Graph Algorithms and Applications, 
							Special issue on Selected papers from the Twenty-fourth International Symposium on Graph Drawing and Network Visualization, GD 2016
					, Tome 21 (2017) no. 5, pp. 823-856. doi : 10.7155/jgaa.00441. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00441/

Cité par Sources :