Введение
Отрасль математической области теории графов – изучение встраивания графов. В математике топологическая теория графов является частью теории графов. Она изучает встраивание графов на поверхности, пространственное встраивание графов и графы как топологические пространства. Также изучаются погружения графов. Встраивание графа на поверхность означает, что мы хотим изобразить граф на поверхности, например, на сфере, так, чтобы никакие два ребра не пересекались. Классической задачей встраивания, часто представляемой в виде математической головоломки, является задача о трёх коммуникациях. Другие применения можно найти в производстве электронных схем, где цель состоит в том, чтобы нанести (встроить) схему (граф) на печатную плату (поверхность) без пересечения соединений, что может привести к короткому замыканию.
the study of graph embeddings
In mathematics, topological graph theory is a branch of graph theory. It studies the embedding of graphs in surfaces, spatial embeddings of graphs, and graphs as topological spaces. It also studies immersions of graphs. Embedding a graph in a surface means that we want to draw the graph on a surface, a sphere for example, without two edges intersecting. A basic embedding problem often presented as a mathematical puzzle is the three utilities problem. Other applications can be found in printing electronic circuits where the aim is to print (embed) a circuit (the graph) on a circuit board (the surface) without two connections crossing each other and resulting in a short circuit.
Графы как топологические пространства
К ненаправленному графу можно сопоставить абстрактный симплициальный комплекс C, имеющий одноэлементное множество для каждой вершины и двухэлементное множество для каждого ребра. Геометрическая реализация |C| комплекса состоит из копии единичного интервала [0,1] для каждого ребра, с концами этих интервалов, склеенными вместе в вершинах. В таком представлении вложения графов на поверхность или как подразделения других графов являются обоими примерами топологического вложения, гомеоморфизм графов – это просто специализация топологического гомеоморфизма, понятие связного графа совпадает с топологической связностью, и связный граф является деревом тогда и только тогда, когда его фундаментальная группа тривиальна. Другие симплициальные комплексы, связанные с графами, включают комплекс Уитни или комплекс клик, с множеством для каждой клики графа, и комплекс сопоставлений, с множеством для каждого сопоставления графа (эквивалентно, комплекс клик дополнения линейного графа). Комплекс сопоставлений полного двудольного графа называется шахматным комплексом, поскольку его также можно описать как комплекс множеств не атакующих ладей на шахматной доске.
Примеры исследований
Джон Хопкрофт и Роберт Тарджан разработали способ проверки планарности графа за время, линейное от количества ребер. Их алгоритм делает это, строя вложение графа, которое они называют «пальмовым деревом». Эффективная проверка планарности является фундаментальной для визуализации графов. Фан Чунг и другие исследовали задачу вложения графа в книгу, размещая вершины графа на прямой вдоль корешка книги. Ребра графа рисуются на отдельных страницах таким образом, чтобы ребра, находящиеся на одной странице, не пересекались. Эта задача абстрагирует задачи компоновки, возникающие при трассировке многослойных печатных плат. Вложения графов также используются для доказательства структурных свойств графов посредством теории миноров графов и теоремы о структуре графов.