CG Week 2022: Workshop in Combinatorial Geometry

• Organized by Martin Balko and Pavel Valtr.
• Friday, 10. June 2022, Meitner-Saal 1, Harnack-Haus.
• Part of the CG Week 2022 in Berlin.

Schedule:	up

• 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, Man-Kwun 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 simply-connected closed regions and a one-to-one 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 n-1 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 dynamic-programming 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 great-circles. By slightly relaxing the geometric restrictions ("lines" dont have to be straight and "circles" dont have to be round), we obtain so-called 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 so-called simple topological drawings, which have the same combinatorial properties as straight-line drawings. Since on top of each point set, we can place a straight-line 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 crossing-critical 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 k-crossing-critical 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 k-crossing-critical graphs that do not have drawings with exactly k crossings. Richter and Thomassen proved in 1993 that if G is k-crossing-critical, 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