Algorithmic, structural and complexity aspects of geometric configurations
Project goals
Configurations of points, lines, convex sets and other simple geometric objects in the plane and graphs visualized in the plane belong to the basic structures of computer visualization. In our research we will study some important algorithmic, structural and complexity questions on basic combinatorial and convex properties of graph drawings in the plane, point sets and other configurations in the plane. We will deal mainly with various types of graph drawings in the plane, crossing numbers. Erdős-Szekeres theorem and extremal questions for selected types of geometric configurations. Full or partial solution of some important open problems is expected.
Keywords
discrete and computational geometrydiscrete mathematicstopologygraph drawingvisibility graphalgebraic methodspoint setsEuclidean spacegeometric graphtopological graphcrossing numbers
Public support
Provider
Czech Science Foundation
Programme
Standard projects
Call for proposals
SGA0202100005
Main participants
Univerzita Karlova / Matematicko-fyzikální fakulta
Contest type
VS - Public tender
Contract ID
21-32817S
Alternative language
Project name in Czech
Algoritmické, strukturální a složitostní aspekty geometrických konfigurací
Annotation in Czech
Konfigurace bodů, přímek, konvexních množin a dalších jednoduchý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 budeme studovat 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ů, množin bodů, konvexních množin a dalších konfigurací v rovině. Budeme se zabývat zejména různými typy nakreslení grafu do roviny, průsečíková čísla, Erdősovu-Szekeresovu větu a extremální otázky pro vybrané typy geometrických konfigurací. Očekává se úplné nebo částečné ř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
Solution timeline
Realization period - beginning
Jan 1, 2021
Realization period - end
Jun 30, 2024
Project status
—
Latest support payment
Apr 1, 2024
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
CEP25-GA0-GA-R
Data delivery date
Mar 12, 2025
Finance
Total approved costs
4,397 thou. CZK
Public financial support
3,920 thou. CZK
Other public sources
477 thou. CZK
Non public and foreign sources
0 thou. CZK
Basic information
Recognised costs
4 397 CZK thou.
Public support
3 920 CZK thou.
89%
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. 2021 - 30. 06. 2024