Optimal Sankey Diagrams via Integer Programming

David Cheng Zarate; Pierre Le Bodic; Tim Dwyer; Graeme Gange; Peter Stuckey

doi:10.1109/PacificVis.2018.00025

Optimal Sankey Diagrams via Integer Programming

David Cheng Zarate, Pierre Le Bodic, Tim Dwyer, Graeme Gange, Peter Stuckey

Research output: Chapter in Book/Report/Conference proceeding › Conference Paper › Research › peer-review

5 Citations (Scopus)

Abstract

We present the first practical Integer Linear Programming model for Sankey Diagram layout. We show that this approach is viable in terms of running time for reasonably complex diagrams and also that the quality of the layout is measurably and visibly better than heuristic approaches in terms of crossing reduction. Finally, we demonstrate that the model is easily extensible through the addition of constraints, such as arbitrary grouping of nodes.

Original language	English
Title of host publication	Proceedings - 2018 IEEE Pacific Visualization Symposium, PacificVis 2018
Subtitle of host publication	10–13 April 2018 Kobe, Japan
Editors	Stefan Bruckner, Koji Koyamada, Bongshin Lee
Place of Publication	Piscataway NJ USA
Publisher	IEEE, Institute of Electrical and Electronics Engineers
Pages	135-139
Number of pages	5
ISBN (Electronic)	9781538614242
DOIs	https://doi.org/10.1109/PacificVis.2018.00025
Publication status	Published - 2018
Event	IEEE Pacific Visualization Symposium 2018 - Kobe, Japan Duration: 10 Apr 2018 → 13 Apr 2018 Conference number: 11th http://research.cbs.chula.ac.th/pvis2019/home.aspx https://ieeexplore.ieee.org/xpl/conhome/8365785/proceeding (Proceedings)

Conference

Conference	IEEE Pacific Visualization Symposium 2018
Abbreviated title	PacificVis 2018
Country	Japan
City	Kobe
Period	10/04/18 → 13/04/18
Internet address	http://research.cbs.chula.ac.th/pvis2019/home.aspx https://ieeexplore.ieee.org/xpl/conhome/8365785/proceeding (Proceedings)

Keywords

graph drawings
integer programming
Visualization

Access to Document

10.1109/PacificVis.2018.00025

Link to publication in Scopus

Cite this

Zarate, D. C., Bodic, P. L., Dwyer, T., Gange, G., & Stuckey, P. (2018). Optimal Sankey Diagrams via Integer Programming. In S. Bruckner, K. Koyamada, & B. Lee (Eds.), Proceedings - 2018 IEEE Pacific Visualization Symposium, PacificVis 2018: 10–13 April 2018 Kobe, Japan (pp. 135-139). IEEE, Institute of Electrical and Electronics Engineers. https://doi.org/10.1109/PacificVis.2018.00025

Zarate, David Cheng ; Bodic, Pierre Le ; Dwyer, Tim ; Gange, Graeme ; Stuckey, Peter. / Optimal Sankey Diagrams via Integer Programming. Proceedings - 2018 IEEE Pacific Visualization Symposium, PacificVis 2018: 10–13 April 2018 Kobe, Japan. editor / Stefan Bruckner ; Koji Koyamada ; Bongshin Lee. Piscataway NJ USA : IEEE, Institute of Electrical and Electronics Engineers, 2018. pp. 135-139

@inproceedings{642ff698dc844f158b58f489aad69db9,

title = "Optimal Sankey Diagrams via Integer Programming",

abstract = "We present the first practical Integer Linear Programming model for Sankey Diagram layout. We show that this approach is viable in terms of running time for reasonably complex diagrams and also that the quality of the layout is measurably and visibly better than heuristic approaches in terms of crossing reduction. Finally, we demonstrate that the model is easily extensible through the addition of constraints, such as arbitrary grouping of nodes.",

keywords = "graph drawings, integer programming, Visualization",

author = "Zarate, {David Cheng} and Bodic, {Pierre Le} and Tim Dwyer and Graeme Gange and Peter Stuckey",

year = "2018",

doi = "10.1109/PacificVis.2018.00025",

language = "English",

pages = "135--139",

editor = "Bruckner, {Stefan } and Koyamada, {Koji } and Bongshin Lee",

booktitle = "Proceedings - 2018 IEEE Pacific Visualization Symposium, PacificVis 2018",

publisher = "IEEE, Institute of Electrical and Electronics Engineers",

address = "United States of America",

note = "IEEE Pacific Visualization Symposium 2018, PacificVis 2018 ; Conference date: 10-04-2018 Through 13-04-2018",

url = "http://research.cbs.chula.ac.th/pvis2019/home.aspx, https://ieeexplore.ieee.org/xpl/conhome/8365785/proceeding",

}

Zarate, DC, Bodic, PL , Dwyer, T , Gange, G & Stuckey, P 2018, Optimal Sankey Diagrams via Integer Programming. in S Bruckner, K Koyamada & B Lee (eds), Proceedings - 2018 IEEE Pacific Visualization Symposium, PacificVis 2018: 10–13 April 2018 Kobe, Japan. IEEE, Institute of Electrical and Electronics Engineers, Piscataway NJ USA, pp. 135-139, IEEE Pacific Visualization Symposium 2018, Kobe, Japan, 10/04/18. https://doi.org/10.1109/PacificVis.2018.00025

Optimal Sankey Diagrams via Integer Programming. / Zarate, David Cheng; Bodic, Pierre Le ; Dwyer, Tim ; Gange, Graeme ; Stuckey, Peter.

Proceedings - 2018 IEEE Pacific Visualization Symposium, PacificVis 2018: 10–13 April 2018 Kobe, Japan. ed. / Stefan Bruckner; Koji Koyamada; Bongshin Lee. Piscataway NJ USA : IEEE, Institute of Electrical and Electronics Engineers, 2018. p. 135-139.

Research output: Chapter in Book/Report/Conference proceeding › Conference Paper › Research › peer-review

TY - GEN

T1 - Optimal Sankey Diagrams via Integer Programming

AU - Zarate, David Cheng

AU - Bodic, Pierre Le

AU - Dwyer, Tim

AU - Gange, Graeme

AU - Stuckey, Peter

N1 - Conference code: 11th

PY - 2018

Y1 - 2018

N2 - We present the first practical Integer Linear Programming model for Sankey Diagram layout. We show that this approach is viable in terms of running time for reasonably complex diagrams and also that the quality of the layout is measurably and visibly better than heuristic approaches in terms of crossing reduction. Finally, we demonstrate that the model is easily extensible through the addition of constraints, such as arbitrary grouping of nodes.

AB - We present the first practical Integer Linear Programming model for Sankey Diagram layout. We show that this approach is viable in terms of running time for reasonably complex diagrams and also that the quality of the layout is measurably and visibly better than heuristic approaches in terms of crossing reduction. Finally, we demonstrate that the model is easily extensible through the addition of constraints, such as arbitrary grouping of nodes.

KW - graph drawings

KW - integer programming

KW - Visualization

UR - http://www.scopus.com/inward/record.url?scp=85048264535&partnerID=8YFLogxK

U2 - 10.1109/PacificVis.2018.00025

DO - 10.1109/PacificVis.2018.00025

M3 - Conference Paper

AN - SCOPUS:85048264535

SP - 135

EP - 139

BT - Proceedings - 2018 IEEE Pacific Visualization Symposium, PacificVis 2018

A2 - Bruckner, Stefan

A2 - Koyamada, Koji

A2 - Lee, Bongshin

PB - IEEE, Institute of Electrical and Electronics Engineers

CY - Piscataway NJ USA

T2 - IEEE Pacific Visualization Symposium 2018

Y2 - 10 April 2018 through 13 April 2018

ER -

Zarate DC, Bodic PL , Dwyer T , Gange G , Stuckey P. Optimal Sankey Diagrams via Integer Programming. In Bruckner S, Koyamada K, Lee B, editors, Proceedings - 2018 IEEE Pacific Visualization Symposium, PacificVis 2018: 10–13 April 2018 Kobe, Japan. Piscataway NJ USA: IEEE, Institute of Electrical and Electronics Engineers. 2018. p. 135-139 https://doi.org/10.1109/PacificVis.2018.00025