Dokazujeme asymptoticky přesné odhady na počet vrcholů, které vyžadují průnikové grafy polygonů vepsaných do kružnice v optimální reprezentaci. Dále ukazujeme, že přesné určení tohoto partametru je NP-těžký problém. (cs)
We prove asymptotically tight bounds on the number of corners that intersection graphs of polygons require in optimal representations. We also prove that computing this parameter is an NP-hard problem.
We prove asymptotically tight bounds on the number of corners that intersection graphs of polygons require in optimal representations. We also prove that computing this parameter is an NP-hard problem. (en)