More Like this

1. The worst graph layout algorithm ever

   https://doi.org/10.31219/osf.io/4hfy9  

   Di Bartolomeo, Sara; Lang, Matěj; Dunne, Cody (January 2022, Proc. alt.VIS workshop at IEEE VIS)

   Graph layout algorithms strive to improve the utility of node-link visualizations or graph drawings by optimizing for readability criteria. One such criteria that has been widely used is to count edge crossings. Prior work has focused solely on minimizing the number of edge crossings, including provably-optimal layout algorithms for layered graphs. The research community has completely ignored the other side of the coin — can we optimally maximize edge crossings? This paper answers this question in the affirmative. Our WORSTisfimal layout algorithm produces the most unreadable layered graph drawing. It does so by using linear programming to produce a provably-optimally-awful solution. We hope that this groundbreaking result opens up an entirely new field of inquiry for graph drawing researchers — optimally-worst layout algorithms. 

   more » « less
2. On the Worst-Case Inefficiency of CGKA

   Alexander Bienstock, Yevgeniy Dodis (January 2022, TCC 2022)
3. Beyond worst-case analysis

   https://doi.org/10.1145/3232535  

   Roughgarden, Tim (February 2019, Communications of the ACM)
4. On the Computation of Worst Attacks: a LP Framework

   https://doi.org/10.23919/ACC.2018.8431670  

   Hirzallah, Nabil H.; Voulgaris, Petros G. (June 2018, 2018 Annual American Control Conference)
5. Worst-case analysis of clique MIPs

   https://doi.org/10.1007/s10107-021-01706-2  

   Naderi, Mohammad Javad; Buchanan, Austin; Walteros, Jose L. (September 2022, Mathematical Programming)