The local crossing number ${\rm LCR(G)}$ of a graph $G$ is defined as the least nonnegative integer $k$ such that the graph has a $k$-planar drawing. In other words, it is the smallest possible number of times that a single edge in a graph is crossed over all possible graph drawings. Is there any known upper bound of ${\rm LCR(G)}$ in terms of the maixmum degree $\Delta(G)$, or in terms of other graph parameters, such of the number of vertices or edges or anything else?
$\begingroup$
$\endgroup$
1
-
$\begingroup$ Sure: if $G$ has $n$ edges, then placing points randomly in the plane and using straight-line edges will yield at most $n-1$ crossings of a single edge. Not a very good upper bound, but it's certainly a known one! $\endgroup$– RavenclawPrefectCommented Nov 11 at 10:24
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
There are constant-degree graphs with local crossing number $\Omega(m)$, where $m = |E(G)|$, for example constant-degree expander graphs (the crossing number of expander graphs is $\Omega(m^2)$, since the bisection width is $\Omega(m)$, see 10.1016/j.jctb.2003.09.002). It shouldn't be too hard to construct simpler explicit examples, based on $n \times n$ meshes (with an additional edge connecting two vertices that are far apart in the mesh, and far from the boundary), for example, though proving the local crossing number lower bound will require some work.
