On Arrangements of Orthogonal Circles

2019/07/18 by Chaplick, Steven, Förster, Henry, Kryven, Myroslav +1
#Computational Geometry (cs.CG) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.1907.08121

Abstract

In this paper, we study arrangements of orthogonal circles, that is, arrangements of circles where every pair of circles must either be disjoint or intersect at a right angle. Using geometric arguments, we show that such arrangements have only a linear number of faces. This implies that orthogonal circle intersection graphs have only a linear number of edges. When we restrict ourselves to orthogonal unit circles, the resulting class of intersection graphs is a subclass of penny graphs (that is, contact graphs of unit circles). We show that, similarly to penny graphs, it is NP-hard to recognize orthogonal unit circle intersection graphs.

Related

• Arrangements of orthogonal circles with many intersections
• Arrangements of Pseudocircles: On Circularizability
• Producing circle patterns via configurations
• Combinatorial Properties of Triangle-Free Rectangle Arrangements and the\n Squarability Problem
• A note on lenses in arrangements of pairwise intersecting circles in the plane