Project

Back to overview

Arrangements of Geometric Objects and Topological Graphs

Applicant Fulek Radoslav
Number 146705
Funding scheme Fellowships for prospective researchers
Research institution Department of Industrial Engineering and Operations Research Columbia University
Institution of higher education Institution abroad - IACH
Main discipline Mathematics
Start/End 01.09.2013 - 28.02.2015
Show all

Keywords (10)

equivariant map; planar graph; convex geometry; arrangment of geometric objects; extremal combinatorics; Euclidean geometry; The Centerpoint Theorem; topological graph; crossing number; clustered planarity

Lay Summary (French)

Lead
Lors de l'affichage de nombreux objets sur un écran d'ordinateur, il est souvent souhaitable d'éviter tout chevauchement entre lesdes paires d'objets autant que possible. Toutefois, la sélection la plus large possible du nombre d'objets qui peuvent être affichés simultanément sans chevauchement est une tâche algorithmiquement difficilemême pour des formes très simples telles que des rectangles dont les côtés sont horizontaux et verticaux.
Lay summary
L'objectif principal de ce projet est d'étudier les propriétés combinatoires des collections de formes géométriques simples, telles que des rectangles, des triangles, des courbes etc., tracées dans le plan. La meilleure compréhension de ces propriétés pourrait être utile dans la conception des algorithmes rapides pour des problèmes de visualisation, mais pourrait aussi avoir un impact sur le développement des autres parties des mathématiques, notamment la théorie des graphes.

Un graphe peut être représenté comme un ensemble de courbes reliant des paires de points dans un ensemble donné. Une telle représentation d'un graphe est appelé un dessin du graphe. Pour un graphe donné, nous sommes intéressés, entre autres, aux questions suivantes. Quel est le nombre minimum de croisements d'arêtes dans un dessin de ce graphe dans le plan? Est-il toujours le même nombre que le nombre minimum de paires d'arêtes qui se croisent? Étonnamment, il reste un problème ouvert pour déterminer s'il existe un graphe pour lequel la réponse à la dernière question est négative.

Nous pouvons également représenter un graphe comme un graphe d'intersection d'objets géométriques. Dans un graphe d'intersection d'objets géométriques, les sommets représentent les objets et deux objets
sont reliés par une arête si ils se croisent. Les graphes d'intersection d'objets géométriques partagent de nombreuses propriétés intéressantes avec la famille des graphes parfaits. Dans ce projet, j'ai également l'intention d'explorer les liens entre les graphes parfaits et les graphes d'intersection.
Direct link to Lay Summary Last update: 07.02.2013

Responsible applicant and co-applicants

Publications

Publication
Clustered planarity testing revisited
Radoslav Fulek, Jan Kynčl, Igor Malinović, Dömötör Pálvölgyi (2015), Clustered planarity testing revisited.
Crossing Numbers and Combinatorial Characterization of Monotone Drawings of Kn
Martin Balko, Jan Kynčl (2015), Crossing Numbers and Combinatorial Characterization of Monotone Drawings of Kn, in Discrete & Computational Geometry, 53(1), 107-143.
Toward the Hanani-Tutte Theorem for Clustered Graphs
Fulek Radoslav (2014), Toward the Hanani-Tutte Theorem for Clustered Graphs.
Towards the Hanani-Tutte Theorem for Clustered Graphs
Fulek Radoslav (2014), Towards the Hanani-Tutte Theorem for Clustered Graphs, in Graph-Theoretic Concepts in Computer Science - 40th International Workshop, {WG} 2014, Nouan-le-Fuzelier, France.

Collaboration

Group / person Country
Types of collaboration
Michael Pelsmajer, IIT, Chicago United States of America (North America)
- in-depth/constructive exchanges on approaches, methods or results
Marcus Schaefer, DePaul University, Chicago United States of America (North America)
- in-depth/constructive exchanges on approaches, methods or results
Pavel Valtr, KAM, Charles University, Prague Czech Republic (Europe)
- in-depth/constructive exchanges on approaches, methods or results
- Publication
Radoš Radoicic, Baruch College, New York City United States of America (North America)
- in-depth/constructive exchanges on approaches, methods or results

Scientific events

Active participation

Title Type of contribution Title of article or contribution Date Place Persons involved
NYU Geometry Seminar Individual talk Vertical Visibility among Parallel Polygons in Three Dimensions 24.02.2015 New York City, United States of America Fulek Radoslav;
Applied Mathematics Department Colloquium Individual talk Title: Clustered Planarity Testing Revisited 04.02.2015 Chicago, United States of America Fulek Radoslav;
Columbia Discrete Math Seminar Individual talk Clustered planarity of Trees via Strip-Trees 02.12.2014 New York City, United States of America Fulek Radoslav;
NYU Geometry Seminar Individual talk Clustered planarity testing for trees 07.10.2014 New York City, United States of America Fulek Radoslav;
Oberwolfach Workshop on Discrete Geometry Talk given at a conference Toward the Hanani–Tutte Theorem for Clustered Graphs 31.08.2014 Oberwolfach, Germany Fulek Radoslav;
SUMMIT240 Talk given at a conference Z2-embeddings of Clustered Graphs 07.07.2014 Budapest, Hungary Fulek Radoslav;
Combinatorial Algorithms Day Talk given at a conference Towards the Hanani-Tutte Theorem for Clustered Graphs 30.06.2014 Zurich, Switzerland Fulek Radoslav;
WG 2014 Talk given at a conference Towards the Hanani-Tutte Theorem for Clustered Graphs 25.06.2014 Le Domaine de Chalès, near Orléans, France Fulek Radoslav;
NYU Geometry Seminar Individual talk Crossing Numbers and Combinatorial Characterization of Monotone Drawings of Kn. 04.02.2014 New York City, United States of America Fulek Radoslav;
Poly Theory Seminar Individual talk Z2-embeddings of clustered graphs 21.11.2013 New York City, United States of America Fulek Radoslav;
Columbia Discrete Math Seminar Individual talk Universal Point Sets for Planar Three-Trees 22.10.2013 New York City, United States of America Fulek Radoslav;
BIRS Workshop on Geometric and Topological Graph Theory Talk given at a conference Recent Progress on the Hill's Conjecture 01.10.2013 Banff, Canada Fulek Radoslav;


Abstract

My aim in this project is to solve selected combinatorial problems aboutarrangements of basic geometric objects such as points, lines, curves,polygons, polyhedra, discs, convex sets etc. Closely related to this, I alsointend to work on problems in topological graph theory, which can be regarded as the study of arrangements of curves on a fixed set of endpoints. My project is divided into two parts.In the first part I want to address the three following types of problemsabout geometrically defined graphs and hypergraphs.1. I plan to work on cover-decomposability problems in which we ask for a given set of geometric shapes, if for a given L there exists a number K such that any K-fold cover of the space by given geometric shapes can be decomposed into L covers.2. By using methods of structural graph theory I plan to attack problemsrelated to the quasi-perfectness of intersection graphs of geometric objects. Thus, my main goal in this part of the project is to investigate the relation between the chromatic and clique number in intersection graphs of selected classes of geometric objects.3. I intend to prove some variants or generalizations of The CenterpointTheorem by employing methods of algebraic topology.The second part of my project deals with topological graphs, and it is centered around the following questions.1. What is the minimum number of pairs of crossing edges in a drawing of a graph in the plane? Is this number always the same as the minimum number of edge crossings in such a drawing?2. Can we test whether a clustered graph admits a clustered planar drawing in polynomial time?3. What is the maximal density of edges in a topological graph avoidinga given configuration?
-