 Organized by Martin Balko and Pavel Valtr.
 Friday, 10. June 2022, MeitnerSaal 1, HarnackHaus.
 Part of the CG Week 2022 in Berlin.
 14:30 – 15:00 Alexandra Weinberger: Gioan's Theorem for complete bipartite graphs
 Abstract: A drawing is simple if each pair of edges has at most one common point. For any two simple drawings of the complete graph K_n with the same crossing edge pairs, Gioan's Theorem states that one drawing can be transformed into the other by a sequence of triangle flips (a.k.a Reidemeister moves of Type 3). Intuitively, this operation refers to the act of moving one edge of a triangular cell formed by three pairwise crossing edges over the opposite vertex of the cell.
In this talk, we consider to what extent Gioan's Theorem generalizes to other classes of graphs. On the one hand, we show that it holds for complete bipartite graphs K_{m,n} under similar requirements. On the other hand, the theorem does not hold if the graph is slightly sparser. For example, it does not hold if we remove any two edges from K_{m,n}.
(Joint work with Oswin Aichholzer, ManKwun Chiu, Hung P. Hoang, Michael Hoffmann, Yannic Maus, and Birgit Vogtenhuber).
 15:00 – 15:30 Michael Hoffmann: Bounding and computing obstacle numbers of graphs
 Abstract: An obstacle representation of a graph G consists of a set of pairwise
disjoint simplyconnected closed regions and a onetoone mapping of
the vertices of G to points such that two vertices are adjacent in G
if and only if the line segment that connects the two corresponding
points does not intersect any obstacle. The convex obstacle number of
a graph is the smallest number of obstacles in an obstacle
representation of the graph where all obstacles are convex
polygons. In this talk, I will discuss some recent results, in
particular, a linear lower bound for the convex obstacle number: there
is a constant c s.t. for every n there exists a graph on n vertices
that has convex obstacle number at least cn.
Joint work with Martin Balko, Steven Chaplick, Robert Ganian,
Siddharth Gupta, Pavel Valtr, and Alexander Wolff.
 15:30 – 16:00 Cofee break
 16:00 – 16:30 Günter Rote: Enumeration and counting of pseudoline arrangements
 Abstract: I will describe how I could recently determine, with the help of
a computer, the number of pseudoline arrangements of up
to 16 pseudolines [OEIS A006245], in about 6 months of CPU time.
The basis is the straightforward recursive enumeration algorithm, which visits
all pseudoline arrangements by threading an additional pseudoline
into an arrangement of n1 pseudolines.
In this way, one can easily visit the 24698 arrangements of 7 pseudolines.
For each such arrangement P, we counted the
ways of threading 9 additional pseudolines through P.
This is computed in a dynamicprogramming manner, by sweeping
a rope across P from the bottom to the top face, and
maintaining, for each position of the rope, the
ways how the 9 additional pseudolines can intersect the rope.
When advancing the rope across a face, one needs information
about the number of "partial" pseudoline arrangements, in which not every
pair of pseudolines has to cross. This information is computed in a preprocessing step by
the same enumeration algorithm.
 16:30 – 17:00 Manfred Scheucher: Structures from combinatorial geometry and their encodings
 Abstract: Point, lines, and circles are some of the fundamental entities from
geometry.
In this talk we discuss the underlying combinatorics of point configurations
and their dual structures: arrangements of lines and arrangements of
greatcircles.
By slightly relaxing the geometric restrictions
("lines" dont have to be straight and "circles" dont have to be round),
we obtain socalled pseudopoint configurations,
arrangements of pseudolines and (great)pseudocircles, respectively.
While the original settings cannot be axiomized via finitely many
forbidden subconfigurations,
we can indeed find such a purely combinatorial describtion for the
relaxed "pseudo" setting
which allows us to make investigations using computer assistance,
and in particular, using SAT attacks.
Last but not least, we discuss socalled simple topological drawings,
which have the same combinatorial properties as straightline drawings.
Since on top of each point set, we can place a straightline drawing of
the complete graph,
simple topological drawings can be seen as a further generalization of
point configurations
(they indeed also generalize pseudopoint configurations).
 17:00 – 17:30 Géza Tóth: Crossing number of crossingcritical graphs
 Abstract: The crossing number of a graph G is the minimum number of edge crossings over all drawings of G in the plane.
A graph G is kcrossingcritical if its crossing number is at least k, but if we remove any edge of G, its crossing number drops below k.
There are examples of kcrossingcritical graphs that do not have drawings with exactly k crossings.
Richter and Thomassen proved in 1993 that if G is kcrossingcritical, then its crossing number is at most 2.5k+16.
We improve this bound to 2k+6\sqrt{k}+47.
 17:30 – 18:00 Martin Balko and Pavel Valtr: Some open problems in combinatorial geometry
