Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.
We show that there exist series-parallel graphs requiring Omega(n2(root log n)) area in any straight-line or poly-line grid drawing. Such a result is achieved in two steps. First, we show that, in any straight-line or poly-line drawing of K-2,K-n, one side of the bounding box has length Omega(n), thus answering two questions posed by Biedl et al. Second, we show a family of series-parallel graphs requiring Omega(2(root log n)) width and Omega(2(root log n)) height in any straight-line or poly-line grid drawing. Combining the two results, the Omega(n2(root log n)) area lower bound is achieved.
Alexandre Massoud Alahi, Yang Gao, Kaouther Messaoud Ben Amor, Saeed Saadatnejad
Haitham Al Hassanieh, Junfeng Guan, Seyedsohrab Madani, Saurabh Gupta, Waleed Ahmed
, , ,