Algorithmic, structural and complexity aspects of geometric and other configurations
Project goals
Configurations of points, of lines and of other geometric objects in the plane, and graphs drawn in the plane belong to the basic structures of computer visualization. In our research we will focus on some algorithmic, structural and complexity questions on basic combinatorial and convex properties of graph drawings in the plane and of other planar and related configurations. Areas of our interest include graph drawings, crossing numbers, Erdös-Szekeres theorem, extremal questions for selected types of configurations. We expect to find full or partial solution to some important open problems.
Keywords
graph drawingplanepointlineconvex setconvex polygongeometric algorithmsmatricecrossing numbers
Public support
Provider
Czech Science Foundation
Programme
Standard projects
Call for proposals
Standardní projekty 22 (SGA0201800001)
Main participants
Univerzita Karlova / Matematicko-fyzikální fakulta
Contest type
VS - Public tender
Contract ID
18-19158S
Alternative language
Project name in Czech
Algoritmické, strukturální a složitostní aspekty geometrických a dalších konfigurací
Annotation in Czech
Konfigurace bodů, přímek a dalších geometrických objektů v rovině a grafy zobrazené v rovině patří k základním strukturám při počítačové vizualizaci. Ve výzkumu se zaměříme na některé důležité algoritmické, strukturální a složitostní otázky týkající se základních kombinatorických a konvexních vlastností rovinných nakreslení grafů a dalších rovinných a souvisejících konfigurací. Oblasti našeho zájmu zahrnují kreslení grafů do roviny, průsečíková čísla, Erdös-Szekeresovu větu a extemální otázky pro vybrané typy konfigurací. Předpokládáme nalezení úplného nebo částečného řešení některých důležitých otevřených problémů.
Scientific branches
R&D category
ZV - Basic research
OECD FORD - main branch
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
OECD FORD - secondary branch
—
OECD FORD - another secondary branch
—
AF - Documentation, librarianship, work with information
BC - Theory and management systems
BD - Information theory
IN - Informatics
Completed project evaluation
Provider evaluation
U - Uspěl podle zadání (s publikovanými či patentovanými výsledky atd.)
Project results evaluation
The project outcomes are fulfilling the original goals, which is evidenced by the numerous publications associated with the project. A positive aspect is that the project involved many junior researchers and students. In my opinion, the project was successfully completed.
Solution timeline
Realization period - beginning
Jan 1, 2018
Realization period - end
Dec 31, 2021
Project status
U - Finished project
Latest support payment
Apr 1, 2021
Data delivery to CEP
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data delivery code
CEP22-GA0-GA-U
Data delivery date
Jun 29, 2022
Finance
Total approved costs
4,846 thou. CZK
Public financial support
3,657 thou. CZK
Other public sources
1,184 thou. CZK
Non public and foreign sources
0 thou. CZK
Basic information
Recognised costs
4 846 CZK thou.
Public support
3 657 CZK thou.
75%
Provider
Czech Science Foundation
OECD FORD
Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Solution period
01. 01. 2018 - 31. 12. 2021