Conditions on square geometric graphs

Abstract

For any metric $d$ on ${\mathbb{R}}^2$, an (${\mathbb{R}}^2,d$)-geometric graph is a graph whose vertices are points in ${\mathbb{R}}^2$, and two vertices are adjacent if and only if their distance is at most 1. If $d=\Vert .{\Vert }_{\infty }$, the metric derived from the $L_{\infty }$ norm, then $({\mathbb{R}}^2,\Vert .{\Vert }_{\infty })$-geometric graphs are precisely those graphs that are the intersection of two unit interval graphs. We refer to $({\mathbb{R}}^2,\Vert .{\Vert }_{\infty })$-geometric graphs as square geometric graphs. We represent a characterization of square geometric graphs. Using this characterization we provide necessary conditions for the class of square geometric $B_{a,b}$-graphs, a generalization of cobipartite graphs. Then by applying some restrictions on these necessary conditions we obtain sufficient conditions for $B_{a,b}$-graphs to be square geometric.