Arrangements of Pseudocircles and Circles

作者：Kang Ross J; Mueller Tobias

来源：Discrete & Computational Geometry, 2014, 51(4): 896-925.

DOI：10.1007/s00454-014-9583-8

• Arrangements
• Pseudocircles
• Intersection graphs

An arrangement of pseudocircles is a finite collection of Jordan curves in the plane with the additional properties that (i) every two curves meet in at most two points; and (ii) if two curves meet in a point , then they cross at . We say that two arrangements and are equivalent if there is a homeomorphism of the plane onto itself such that for all . Linhart and Ortner (Beitrage Algebra Geom 46:351-356, 2005) gave an example of an arrangement of five pseudocircles that is not equivalent to an arrangement of circles, and they conjectured that every arrangement of at most four pseudocircles is equivalent to an arrangement of circles. Here we prove their conjecture. We also consider two related recognition problems. The first is the problem of deciding, given a (combinatorial description of a) pseudocircle arrangement, whether it is equivalent to an arrangement of circles. The second is deciding whether it is equivalent to an arrangement of convex pseudocircles. We prove that both problems are NP-hard, answering questions of Bultena et al. (11th Canadian Conference on Computational Geometry, 1998) and of Linhart and Ortner (Geombinatorics 18:66-71, 2008). We also give an example of an arrangement of convex pseudocircles with the property that its intersection graph (i.e. the graph with one vertex for each pseudocircle and an edge between two vertices if and only if the corresponding pseudocircles intersect) cannot be realised as the intersection graph of a family of circles. This disproves a folklore conjecture communicated to us by Pyatkin.

• 出版日期2014-6