Arrangements of orthogonal circles with many intersections

DOI10.1007/978-3-030-92931-2_24MaRDI QIDQ6369634arXivFDO

Authors Sarah Carmesin, André Schulz

Publication date 7 June 2021

Published in arXiv

Full work available at URL https://doi.org/10.1007/978-3-030-92931-2_24

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

arXiv classification

cs.CGmath.CO

Abstract: An arrangement of circles in which circles intersect only in angles of $pi/2$ is called an emph{arrangement of orthogonal circles}. We show that in the case that no two circles are nested, the intersection graph of such an arrangement is planar. The same result holds for arrangement of circles that intersect in an angle of at most $pi/2$. For the general case we prove that the maximal number of edges in an intersection graph of an arrangement of orthogonal circles lies in between $4n-Oleft(sqrtnight)$ and $left(4+frac511ight)n$, for $n$ being the number of circles. Based on the lower bound we can also improve the bound for the number of triangles in arrangements of orthogonal circles to $(3+5/9)n-Oleft(sqrtnight)$.

This page was built for publication: Arrangements of orthogonal circles with many intersections

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6369634)