THEMATIC PROGRAMS

December 21, 2014

Mini-symposium on Geometric Representations of Graphs
April 11 - 14, 2000

Schedule

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