| However, there exist graphs that have a greedy embedding in the Euclidean plane but for which no spanning tree has a greedy embedding. | Тем не менее, существуют графы, имеющие жадное вложение в евклидову плоскость, но стягивающие деревья для этих графов жадного вложения не имеют. |
| The R stands for "rigid": in the application of SPQR trees in planar graph embedding, the associated graph of an R node has a unique planar embedding. | «Rigid» здесь означает, что при применении SPQR-деревьев для планарного вложения графа ассоциированный с узлом R граф имеет единственное планарное вложение. |
| For k > 1 a planar embedding is said to be k-outerplanar if removing the vertices on the outer face results in a (k - 1)-outerplanar embedding. | Для к > 1 говорят, что планарное вложение является k-внешнепланарным, если удаление вершины из внешней грани приводит к (k - 1)-внешнепланарному вложению. |
| Testing whether a directed graph with a fixed planar embedding can be drawn upward planar, with an embedding consistent with the given one, can be accomplished by checking that the embedding is bimodal and modeling the consistent assignment problem as a network flow problem. | Проверку, можно ли ориентированный граф с фиксированным планарным вложением нарисовать как восходящий планарный с совместимым вложением, можно выполнить путём проверки, что вложение является бимодальным, и моделирования задачи совместимого назначения как задачи о потоке в сети. |
| For more general graphs, some greedy embedding algorithms such as the one by Kleinberg start by finding a spanning tree of the given graph, and then construct a greedy embedding of the spanning tree. | Для более общих классов графов некоторые алгоритмы нахождения жадного вложения, как, например, алгоритм Клейнберга, начинают с поиска остовного дерева заданного графа, а затем строят жадное вложение этого остовного дерева. |
| The class of trees that admit greedy embeddings into the Euclidean plane has been completely characterized, and a greedy embedding of a tree can be found in linear time when it exists. | Класс деревьев, позволяющий жадное вложение в евклидово пространство, может быть полностью охарактеризирован, и жадное вложение дерева может быть найдено за линейное время, если таковое вложение существует. |
| White (2001) finds embeddings of the Paley graphs of order q = 1 (mod 8) that are highly symmetric and self-dual, generalizing a natural embedding of the Paley graph of order 9 as a 3×3 square grid on a torus. | Уайт (White, 2001) нашёл вложение графов Пэли порядка q = 1 (mod 8), обобщая естественное вложение графа Пэли 9-го порядка как квадратной решётки на тор. |
| The projective plane embedding can also be formed from the standard pentagonal drawing of the Petersen graph by placing a cross-cap within the five-point star at the center of the drawing, and routing the star edges through this cross-cap; the resulting drawing has six pentagonal faces. | Вложение в проективную плоскость можно также образовать из стандартного пятиугольного рисунка графа Петерсена путём помещения плёнки (разрезанной бутылки Кляйна) внутрь пятиугольной звезды в центре рисунка и направления рёбер звезды через эту плёнку. |
| Other pairs of graph types that always admit a simultaneous embedding, but that might need larger grid sizes, include a wheel graph and a cycle graph, a tree and a matching, or a pair of graphs both of which have maximum degree two. | Другие пары графов, позволяющие одновременное вложение, но, возможно, требующие больших размеров решётки, это колесо и цикл, дерево и паросочетание, а также пары графов, у которых максимальная степень равна двум. |
| Two-page book embedding has also been used to find simultaneous embeddings of graphs, in which two graphs are given on the same vertex set and one must find a placement for the vertices in which both graphs are drawn planarly with straight edges. | Двухстраничное книжное вложение используется также для поиска одновременного вложения графов, при котором два графа заданы на одном множестве вершин, и нужно найти расположение вершин, при котором оба графа рисуются планарно с помощью прямых отрезков. |
| The classification of different types of input as always having an embedding or as sometimes not being possible depends not only on the two types of graphs to be drawn, but also on the structure of their intersection. | Для одновременного вложения с фиксированными рёбрами классификация различных видов входных графов, всегда имеющих вложение или иногда не имеющих вложения, зависит не только от типов двух участвующих графов, но и также от структуры их пересечения. |
| Choose some three vertices a, b, c forming a triangular face of G. We prove by induction on n that there exists a straight-line combinatorially isomorphic re-embedding of G in which triangle abc is the outer face of the embedding. | Выберем некоторые три вершины а, Ь, с, образующие треугольную грань графа G. Мы докажем по индукции по n, что существует комбинаторно изоморфное другое вложение с прямыми рёбрами графа G, в котором треугольник abc является внешней гранью вложения. |