 |
|
|
|
|
||||||||||||||||||||||||||||||||||||||||||||||||
|
|
|
THEMATIC PROGRAMS |
|
||||||||||||||||||||||||||||||||||||||||||||||||
| April 20, 2024 |
|
|||||||||||||||||||||||||||||||||||||||||||||||||||
|
Mini-symposium on Geometric Representations of Graphs
|
|||||||||||||||||||||||||||||||||||||||||||||||||||
| Tuesday April 11 | |
|---|---|
| 11:00 - 12:00 p.m. | Registration and COFFEE |
| 12:00 - 2:00 p.m. | LUNCH |
| 2:00 - 3:00 p.m. | Jan Kratochvil Complexity of recognition of intersection graphs Several classes of intersection graphs will be described. Complexity of their recognition will be discussed, including a general technique for showing NP-hardness and questions about upper bounds. |
| 3:00 - 3:30 p.m. | TEA-TIME |
| 3:30 - 4:30 p.m. | Sue Whitesides Complexity lower bounds for geometric representations of graphs This talk will focus on a technique called the "logic engine", which has proved useful for obtaining NP-hardness results for geometric realization problems for graphs. Several examples of the application of this technique to proximity graph realization problems will be given. |
| 4:40 - 5:30 p.m. | André Kündgen Art gallery problems |
| Wednesday, April 12 | |
| 10:00 - 10:50 a.m. | Petr Hlineny Unit-ball contact graphs |
| 10:50 - 12:00 a.m. | Informal session 1 |
| 12:00 - 2:00 p.m. | LUNCH |
| 2:00 - 3:00 p.m. | Jan Kratochvil Intersection representations of planar graphs and their complements The question of representing planar graphs will be discussed, several partial results and possible generalizations for surfaces of higher genus will be surveyed. |
| 3:00 - 3:30 p.m. | TEA-TIME |
| 3:30 - 4:30 p.m. | Sue Whitesides Some 2D visibility representation for graphs This talk will focus on 2D representations of graphs in which the vertices are represented as horizontal line segments and the edges are represented as vertical lines of sight between these segments. |
| 4:30 - 5:30 p.m. | Informal session 2 |
| Thursday, April 13 | |
| 10:00 - 11:00 a.m. | Sue Whitesides Some 3D visibility representations for graphs This talk will focus on 3D representations of graphs in which the vertices are represented as 2D objects floating in 3D parallel to the xy-plane, and the edges are represented as vertical lines of sight between these objects. |
| 11:10 - 12:00 p.m. | Informal session 3 |
| 12:00 - 2:00 p.m. | LUNCH |
| 2:00 - 3:00 p.m. | Jan Kratochvil Optimization problems for intersection graphs Some classes of intersection graphs allow fast (polynomial time) algorithms for optimization problems such as coloring, maximum clique, maximum independent set etc., that are NP-complete for general graphs. We will discuss the borderline between polynomially solvable and NP-complete instances. The theoretical question of bounding the chromatic number by a function of the clique number will be also mentioned. |
| 3:00 - 3:30 p.m. | TEA TIME |
| 3:30 - 4:30 p.m. | Informal Session 4 |
| 4:40 - 5:30 p.m. | Informal Session 5 |
| Friday, April 14 | |
| Informal collaboration and discussions | |