Towards a better understanding of arrangements of circles and also to get rid of geometric difficulties, we look at the more general setting of ''arrangements of pseudocircles'' which was first introduced by Grünbaum in the 1970's. An arrangement of pseudocircles is a collection of simple closed curves on the sphere or in the plane such that any two of the curves are either disjoint or intersect in exactly two points, where the two curves cross. In his book, Grünbaum conjectured that every digon-free arrangement of n pairwise intersecting pseudocircles contains at least $2n-4$ triangular cells. We present arrangements to disprove this conjecture and give new bounds on the number of triangular cells for various classes of arrangements.
Furthermore, we study the ''circularizability'' of arrangements: it is clear that every arrangement of circles is an arrangement of pseudocircles, however, deciding whether an arrangement of pseudocircles is isomorphic to an arrangement of circles is computationally hard. Using a computer program, we have enumerated all combinatorially different arrangements of up to $7$ pseudocircles. For the class of arrangements of $5$ pseudocircles and for the class of digon-free intersecting arrangements of $6$ pseudocircles, we give a complete classification: we either provide a circle representation or a non-circularizability proof. For these proofs we use incidence theorems like Miquel's and arguments based on continuous deformation, where circles of an assumed circle representation grow or shrink in a controlled way.
This talk summarizes results from two articles, which are both joint work with Stefan Felsner: * Arrangements of Pseudocircles: Triangles and Drawings; short version in Proc. GD'17; full version available at arXiv (1708.06449) * Arrangements of Pseudocircles: On Circularizability; short version in Proc. GD'18; full version in DCG: Ricky Pollack Memorial Issue (doi:10.1007/s00454-019-00077-y)
Jul 01, 2019 | 04:00 PM s.t.
Freie Universität Berlin
Institut für Informatik
Room 005 (Ground Floor)