Two results on intersection graphs of polygons

Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F04%3A00003088" target="_blank" >RIV/00216208:11320/04:00003088 - isvavai.cz</a>
Result on the web
—
DOI - Digital Object Identifier
—

Result language
angličtina
Original language name
Two results on intersection graphs of polygons
Original language description
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.
Czech name
Dva výsledky o průnikových grafech polygonů
Czech description
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.

Type
J<sub>x</sub> - Unclassified - Peer-reviewed scientific article (Jimp, Jsc and Jost)
CEP classification
BA - General mathematics
OECD FORD branch
—

Project
<a href="/en/project/LN00A056" target="_blank" >LN00A056: Institute of Theoretical Computer Science (Center of Young Science)</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)<br>Z - Vyzkumny zamer (s odkazem do CEZ)

Publication year
2004
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Similar results(10)