Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur 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
Mathieu Salzmann, Yinlin Hu, Jingyu Li, Rui Song
Haitham Al Hassanieh, Junfeng Guan, Seyedsohrab Madani, Saurabh Gupta, Waleed Ahmed