"Записки научных семинаров ПОМИ"
Том 488, стр. 49-65
Об изображении 2-планарного графа на плоскости
Д. В. Карпов
С.-Петербургское отделение
Математического института
им. В. А. Стеклова РАН,
Фонтанка 27, 191023 С.-Петербург;
С.-Петербургский
государственный университет,
Университетский пр. 28,
Старый Петергоф,
198504 Санкт-Петербург, Россия
dvk0@yandex.ru
- Аннотация:
В статье доказано, что любой рёберно $(2k+1)$-связный $k$-планарный граф можно изобразить на плоскости так, чтобы любая пара пересекающихся рёбер в этом изображении пересекалась ровно в одной точке. Доказано, что любой $2$-планарный граф можно изобразить так, что любые два пересекающихся ребра не имеют общих концов и пересекаются ровно в одной точке. Кроме того, доказано, что любой 2-планарный граф имеет надграф на том же множестве вершин, который можно изобразить так, чтобы для любой вершины в циклическом порядке выходов ее рёбер среди каждых трёх последовательных рёбер было не менее одного простого ребра. (Ребро называется простым, если оно не пересекает никакое другое ребро в этом изображении).
Библ. -- 5 назв.
- Ключевые слова: 2-планарный граф, плоское изображение графа
[2-planar graph, plane drawing of a graph]
Полный текст(.pdf)