论文标题
任意点集的配对交叉数，切口和良好的图纸
Pair crossing number, cutwidth, and good drawings on arbitrary point sets
论文作者
论文摘要
在几何图理论中，确定是否存在图形，以使其交叉数和对交叉数是不同的开放问题。我们表明，对于每个图$ g $回答Pach和Tóth的问题，我们证明了图$ g $的二宽度宽度（实际上也是cutwidth），$ g $ agre $ g $ agremence $ d_1，d_2，\ d_2，\ dots，d_n $满意$ \ Mathop {\ Mathrm {bw}}（g）= o \ big（\ sqrt {\ Mathop {\ Mathrm {pcr}}}}}（g）+\ sum_ {k = 1}^n d_k^2} \ big）$。然后，我们表明存在一个常数$ c \ geq 1 $，以便以下内容：对于任何图$ g $的订单$ n $和任何至少$ n^c $ s $ s $ s $ s $ s $ n^c $ suptive in Planh in Pland on Plane上的位置，$ g $都可以将顶点映射到$ s $的直线图，并具有$ s $（不超过$ o \ of log） n \ cdot \ left（\ mathop {\ mathrm {pcr}}}}（g）+\ sum_ {k = 1}^n d_k^2 \ right）\ right）$ crossings。我们的证明依赖于Lee的Swiorater定理的修改版本，这可能引起独立的兴趣。
Determining whether there exists a graph such that its crossing number and pair crossing number are distinct is an important open problem in geometric graph theory. We show that $\textit{cr}(G)=O(\mathop{\mathrm{pcr}}(G)^{3/2})$ for every graph $G$, this improves the previous best bound by a logarithmic factor. Answering a question of Pach and Tóth, we prove that the bisection width (and, in fact, the cutwidth as well) of a graph $G$ with degree sequence $d_1,d_2,\dots,d_n$ satisfies $\mathop{\mathrm{bw}}(G)=O\big(\sqrt{\mathop{\mathrm{pcr}}(G)+\sum_{k=1}^n d_k^2}\big)$. Then we show that there is a constant $C\geq 1$ such that the following holds: For any graph $G$ of order $n$ and any set $S$ of at least $n^C$ points in general position on the plane, $G$ admits a straight-line drawing which maps the vertices to points of $S$ and has no more than $O\left(\log n\cdot\left(\mathop{\mathrm{pcr}}(G)+\sum_{k=1}^n d_k^2\right)\right)$ crossings. Our proofs rely on a modified version of a separator theorem for string graphs by Lee, which might be of independent interest.
