ГлавнаяАрхивПроверка планарности и построение топологического рисунка плоского графа (поиском в глубину)

Проверка планарности и построение топологического рисунка плоского графа (поиском в глубину) | Прикладная дискретная математика. 2016. № 2(32).

Рассматривается алгоритм проверки графа на планарность с одновременным построением математических структур для описания топологического рисунка плоского графа. Такими математическими структурами являются изометрические циклы и вращение вершин графа. Показано, что система изометрических циклов графа индуцирует вращение вершин для описания топологического рисунка плоского графа. В отличие от классических алгоритмов проверки планарности, например алгоритма Хопкрофта - Тарьяна, полученный в результате работы алгоритма топологический рисунок используется для визуализации плоского графа. Вычислительная сложность алгоритма определяется как O(m), где m - количество рёбер графа.
  • Title Проверка планарности и построение топологического рисунка плоского графа (поиском в глубину)
  • Headline Проверка планарности и построение топологического рисунка плоского графа (поиском в глубину)
  • Publesher Tomask State UniversityTomsk State University
  • Issue Прикладная дискретная математика 2(32)
  • Date:
  • DOI
Ключевые слова
граф, планарность, визуализация графа, топологический рисунок графа, алгоритмы на графах, вращение вершин, изометрические циклы, graph, planarity, graph visualization, topological graph drawing, graph algorithms, vertices rotation, isometric cycles
Авторы
Ссылки
Курапов С. В., Давидовский М. В. Два подхода к проведению соединений в плоских конструктивах // Компоненты и технологии. 2015. №7. С. 142-147.
Курапов С. В., Давидовский М. В. Топологический подход к проведению соединений в плоских конструктивах // Компоненты и технологии. 2015. №11. С. 127-130.
Апанович З. В. От рисования графов к визуализации информации // Препринт № 148. Новосибирск: ИСИ СО РАН, 2007. 16 c.
Di Battista G., Eades P., Tamassia R., and Tollis I. G. Algorithms for drawing graphs: an annotated bibliography // Comp. Geom. 1994. V.4. No. 5. P. 235-282.
Tamassia R. Handbook of Graph Drawing and Visualization. Boca Raton: Chapman and Hall/CRC, 2013. 844 p.
Курапов С. В., Толок А. В. Методы построения топологического рисунка графа // Автоматика и телемеханика. 2013. №9. C. 78-97.
Kavitha T., Liebchen C., Mehlhorn K., et al. Cycle bases in graphs - characterization, algorithms, complexity, and applications // Comput. Sci. Rev. 2009. No. 3. P. 199-243.
Деза М., Гришухин В. П., Штогрин М. И. Изометрические полиэдральные подграфы в гиперкубах и кубических решетках. М.: МЦНМО, 2007. 192 с.
Рингель Г. Теорема о раскраске карт. М.: Мир, 1977. 126с.
Зыков А. А. Теория конечных графов. Новосибирск: Наука, 1969. 554с.
Свами М., Тхуласираман К. Графы, сети и алгоритмы. М.: Мир, 1984. 455 с.
Харари Ф. Теория графов. М.: Мир, 1973. 300с.
Мак-Лейн С. Комбинаторное условие для плоских графов // Кибернетический сборник. Новая серия. 1970. №7. С. 68-77.
Хопкрофт Дж. Е., ТарьянР.Е. Изоморфизм планарных графов // Кибернетический сборник. Новая серия. 1975. №12. С. 39-61.
Рейнгольд Э., Нивергельт Ю., Део Н. Комбинаторные алгоритмы. Теория и практика. М.: Мир, 1980. 480 с.
Раппопорт Л. И., Мороговский Б. Н., Поливцев С. А. Векторная алгебра пересечений // Многопроцессорные вычислительные структуры. 1982. №2(11). С. 53-56.
Проверка планарности и построение топологического рисунка плоского графа (поиском в глубину) | Прикладная дискретная математика. 2016. № 2(32).
Проверка планарности и построение топологического рисунка плоского графа (поиском в глубину) | Прикладная дискретная математика. 2016. № 2(32).