Здесь: http://www.planarity.org/Klein_elementary_graph_theory.pdf (в главе «Вложения») дано определение комбинаторного вложения плоского графа. (с определением граней и т. д.) Хотя это можно легко использовать для любого графа, они определяют планарный граф как граф, для которого выполняется формула Эйлера (при условии, что граф связан). Вполне понятно, что для любого плоского графа определение граней в комбинаторном встраивании аналогично определению граней в топологическом встраивании. (при условии, что граф связен. В противном случае при комбинаторном встраивании мы будем иметь бесконечную грань для каждого связного компонента)
Вопрос в том, что если для некоторого связного графа его комбинаторное вложение удовлетворяет формуле Эйлера, означает ли это, что этот граф плоский в топологическом смысле (он имеет плоское вложение, т.е. это плоский граф)?
Ответы:
Это действительно меньше о графе как таковом и больше о топологии. Комбинаторное вложение определяет 2-многообразие, топологическое пространство, в котором каждая точка имеет окрестность, гомеоморфную 2-мерному открытому диску: вложение позволяет определить грань, и мы можем определить топологическое пространство, выбрав диск для каждого лицо и склеивание их вместе по краям графа. Хорошо известная теорема в топологии (называемая классификацией 2-многообразий) говорит нам, какие именно 2-многообразия возможны, и все они отличаются друг от друга тем, являются ли они ориентируемыми или имеют одинаковую эйлерову характеристику (или оба ) - см. Http://www.maths.ed.ac.uk/~aar/surgery/zeeman.pdfдля некоторых разумных лекционных заметок на эту тему, которые включают доказательство, которое вы просите. В этой классификации нет других 2-многообразий, имеющих такую же характеристику Эйлера, что и сфера, поэтому, если вы вычислите характеристику Эйлера и обнаружите, что она соответствует формуле для сферы, вы знаете, что ваше вложение должно быть в сфере.
Найти вложение с фактическими геометрическими координатами на плоскости, если у вас есть плоское комбинаторное вложение, не совсем тривиально, но это можно сделать, например, используя теорию шнидерских лесов. У меня есть некоторые лекционные заметки по этому вопросу, например, на http://www.ics.uci.edu/~eppstein/gina/schnyder/ .
источник