Укладка графа

Укла́дка гра́фа (вложение графа), отображение вершин и рёбер графа соответственно в точки и непрерывные кривые некоторого пространства такое, что вершины, инцидентные ребру, отображаются в концы кривой, соответствующей этому ребру.

Правильной укладкой называется укладка, при которой разным вершинам соответствуют различные точки, а кривые, соответствующие рёбрам (исключая их концевые точки), не проходят через точки, соответствующие вершинам, и не пересекаются. Любой граф допускает правильную укладку в трёхмерное пространство. Граф, допускающий правильную укладку на плоскости, называется плоским. Существуют неплоские графы, например графы ${\displaystyle K_{5}}$ (см. рис. 1) и ${\displaystyle K_{3,3}}$ (см. рис. 2). Наименьший род двумерной ориентируемой поверхности, на которой граф ${\displaystyle G}$ допускает правильную укладку, называется родом ${\displaystyle \gamma (G)}$ графа ${\displaystyle G}$. Установлено, в частности, что

${\displaystyle \gamma (K_{n})=\left]{\frac {(n-3)(n-4)}{12}}\right[}$,

где ${\displaystyle K_{n}}$ – полный граф с ${\displaystyle n}$ вершинами, ${\displaystyle \left]a\right[}$ – наименьшее целое число, не меньшее ${\displaystyle a}$;

${\displaystyle \gamma (K_{m,n})=\left]{\frac {(m-2)(n-2)}{4}}\right[}$,

где ${\displaystyle K_{m,n}}$ – полный двудольный граф;

${\displaystyle \gamma (Q_{n})=1+(n-4)\cdot 2^{n-3}}$,

где ${\displaystyle Q_{n}}$ есть ${\displaystyle n}$-мерный куб. Толщиной ${\displaystyle \theta (G)}$ графа ${\displaystyle G}$ называется наименьшее число его плоских подграфов, объединение которых даёт граф ${\displaystyle G}$. Установлено, в частности, что

${\displaystyle \theta (K_{p})=\left[{\frac {p+7}{6}}\right]{\text{ при }}p\neq 9,10;\quad \theta (K_{9})=\theta (K_{10})=3,}$
${\displaystyle theta(Q_{n})=\left]{\frac {n+1}{4}}\right[,}$
${\displaystyle theta(K_{m,n})=\left]{\frac {mn}{2(m+n-2)}}\right[}$

(возможно с несколькими исключениями).

Изучаются также другие числовые характеристики, связанные с укладкой графов, например число скрещиваний – наименьшее число пересечений рёбер, с которым можно уложить данный граф на данной поверхности; крупность – наибольшее число непересекающихся по рёбрам неплоских подграфов в данном графе и др. Рассматриваются также укладки на неориентируемых поверхностях. Вложение графа в ${\displaystyle n}$-мерную целочисленную решётку – это отображение в данную решётку, при котором вершины отображаются в различные узлы решётки, а рёбра идут по линиям решётки.

Задачи об укладках графов на поверхностях и вложениях их в решётки возникают при автоматизированном проектировании ЭВМ, при проектировании коммуникаций и т. д.