%0 Generic %1 chaplick2019arrangements %A Chaplick, Steven %A Förster, Henry %A Kryven, Myroslav %A Wolff, Alexander %D 2019 %K arxiv myown %T On Arrangements of Orthogonal Circles %U http://arxiv.org/abs/1907.08121 %X 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.

@misc{chaplick2019arrangements, 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.}, added-at = {2019-10-02T13:51:01.000+0200}, author = {Chaplick, Steven and Förster, Henry and Kryven, Myroslav and Wolff, Alexander}, biburl = {https://www.bibsonomy.org/bibtex/2ffaf05340e78d878adc472efd9bbac81/chaplick}, description = {[1907.08121] On Arrangements of Orthogonal Circles}, interhash = {907595bec4682a1a3c575759694cf804}, intrahash = {ffaf05340e78d878adc472efd9bbac81}, keywords = {arxiv myown}, note = {cite arxiv:1907.08121Comment: Appears in the Proceedings of the 27th International Symposium on Graph Drawing and Network Visualization (GD 2019)}, timestamp = {2019-10-02T13:51:01.000+0200}, title = {On Arrangements of Orthogonal Circles}, url = {http://arxiv.org/abs/1907.08121}, year = 2019 }