Мотивировка реализуемости графов на поверхностях

[gogoshik]

Здравствуйте!

Подскажите, плиз, чем вызван актуальный интерес к вопросам изучения реализуемости графов на поверхностях (ну например на торе или торе с дыркой)? Как я понимаю, это как то связано с более простыми условиями нахождения фундаментальных групп поверхностей (теорема Зейферта - ван Кампена) или нет? Ну, например, букет из двух окружностей (мультиграф с одной вершиной и двумя петлями) является деформационным ретрактом проколотого тора. Фундаментальная группа такого букета (графа), которую по видимому вчислить проще, будет являться фундаментальной группой проколотого тора.

[alcoholist]

Не знаю, насколько актуальный... Планарные графы занимают исторически важное место среди всех графов. Вот и строим цепочку: реализуемые на сферах (они же плоские), на торах, на кренделях и т.д.
Условие, что поверхность, тут существенно: любой граф может быть нарисован на трехстраничной книжке.
А фундаментальные группы поверхностей и без графов прекрасно себя чувствуют.

[gogoshik]

alcoholist, спасибо!

Ну, а если рассматривать этот вопрос с алгоритмической точки зрения или computer science? То, как я понимаю, проверка вложимости (погружения) графа в поверхность вполне актуальна?

[alcoholist]

Тут, наверное, просто подумать... Граф непланарен, если содержит $K_5$, или $K_{3,3}$
А насчет актуальности не знаю

[Sender]

alcoholist в сообщении #1337419 писал(а):

Граф непланарен, если содержит $K_5$, или $K_{3,3}$

По-моему, такая формулировка некорректна. Ну или следует уточнить, что здесь понимается под "содержит".

[alcoholist]

Sender
я не учебник же пишу) Непонятно -- переспросят

[Someone]

Sender в сообщении #1337428 писал(а):

Ну или следует уточнить, что здесь понимается под "содержит".

Содержит подграф, гомеоморфный $K_5$ или $K_{3,3}$.
Гомеоморфизм графов можно определить чисто комбинаторно.

[gogoshik]

Someone в сообщении #1337430 писал(а):

Содержит подграф, гомеоморфный $K_5$ или $K_{3,3}$.

Доказательства критерия планарности Понтрягина-Куратовского либо длинны, либо трудны. Существуют другие критерии планарности, но как понимаю с ними тоже не так все просто. И в части алгоритмической (вычислительной) сложности. И это только то, что касается вложимости графа в плосокость. Если мы говорим о каких то других поверхностях, то там, наверное, еще все сложнее и может быть поэтому есть актуальный интерес к вопросу, озвученному в начале темы?

И еще. Сейчас модно начинать курсы алгебраической топологии с идеи вложимости графов в поверхности (например, Элементы комбинаторной и дифференциальной топологии, Прасолов В.В.). Может не просто так, видимо это как то влияет на получение серьезных результатов в алгебраической топологии?

[mihaild]

(Про алгоритмы)

gogoshik в сообщении #1337434 писал(а):

И в части алгоритмической (вычислительной) сложности.

Проверять на планарность за линейное время умеют уже больше 40 лет (Hopcroft, Tarjan "Efficient planarity testing",1974).
Как минимум 14 лет (подозреваю, что больше) умеют за линейное время вкладывать графы в плоскость.

Вообще вложение графов в плоскость полезно для визуализации, вложимость в другие двумерные поверхности скорее всего прямого прикладного значения не имеет. Либо (это довольно вероятно) имеет, но я про него не слышал.
(имеет большое прикладное значение вложение графов в $\mathbb{R}^n$ так, чтобы длины ребер не сильно ехали)

[ИСН]

Вложение:

18057662_1857501617795145_676248984900698146_n.png [ 99.18 Кб | Просмотров: 0 ]

https://www.facebook.com/BestTheorems/p ... 617795145/

[sqribner48]

mihaild в сообщении #1337443 писал(а):

Вообще вложение графов в плоскость полезно для визуализации

Не только для визуализации. И еще в алгоритмах для трассировки проводников печатных плат.

mihaild в сообщении #1337443 писал(а):

вложимость в другие двумерные поверхности скорее всего прямого прикладного значения не имеет.

Теоретически можно предположить ее необходимость для трассировки печатных плат, создаваемых на поверхности шара (ну какой-нибудь спутник)
... Или для прорытия связной сети каналов на Луне.
А вообще очень трудно (а может быть и невозможно) заранее предсказать возможность использования математического результата в практической деятельности.