Outerplanar crossing numbers, the circular arrangement problem and isoperimetric functions (Q1773167)

Let \(G\) be an \(n\)-vertex graph and \(V(G)\) and \(E(G)\) its vertex and edge sets. The outerplanar crossing number \(\nu_1\) of \(G\) is the minimum number of edge crossings over all drawings of \(G\) in the plane so that vertices and edges are represented as points on a circle and line segments, respectively. \(f\) is an isoperimetric function for \(G\) if for any \(U\subseteq V(G)\), \(| U| \leq\frac n2\), there are at least \(f(| U| )\) edges between \(U\) and \(V(G)\setminus U\). Given a nonnegative increasing real function \(F\), the generalized circular arrangement problem for \(G\) asks for the minimum of \(\sum_{\{u,v\}\in E(G)}F(d(h(u),h(v)))\) over all bijections \(h:V(G)\to V(C_n)\), where \(d\) denotes the distance of vertices in the \(n\)-cycle \(C_n\). This paper extends a joint work of \textit{F.~Shahrokhi} with three of the present authors [Contemp. Math. 342, 249--258 (2004; Zbl 1062.05050)], using similar methods. The main result provides a general lower bound on \(\nu_1(G)\), expressed in terms of vertex degrees and an isoperimetric function \(f\) of \(G\), provided its difference function \(\Delta f\) defined by \(\Delta f(i)=f(i+1)-f(i)\) is nonnegative and decreasing. As a corollary, the authors obtain lower bounds on the generalized circular arrangement problem. They also employ estimates of isoperimetric functions to derive lower bounds on \(\nu_1\) of hypercubes and Cartesian powers of the Petersen graph and to describe infinite classes of graphs whose \(\nu_1\) exceeds their crossing number by a factor of \(\Theta(\log n)\).