On star-multi-interval pairwise compatibility graphs

A graph $G$ is a star-$k$-PCG if there exists a non-negative edge weighted star tree $S$ and $k$ mutually exclusive intervals $I_1, I_2, \ldots , I_k$ of non-negative reals such that each vertex of $G$ corresponds to a leaf of $S$ and there is an edge between two vertices in $G$ if the distance between their corresponding leaves in $S$ lies in $I_1\cup I_2\cup\ldots \cup I_k$. These graphs are related to different well-studied classes of graphs such as PCGs and multithreshold graphs. It is well known that for any graph $G$ there exists a $k$ such that $G$ is a star-$k$-PCG. Thus, for a given graph $G$ it is interesting to know which is the minimum $k$ such that $G$ is a star-$k$-PCG. In this paper we focus on classes of graphs where $k$ is constant and prove that circular graphs and two dimensional grid graphs are both star-$2$-PCGs and that they are not star-$1$-PCGs. Moreover we show that $4$-dimensional grids are at least star-$3$-PCGs.