Числа пересечения графов - Crossing Numbers of Graphs

Числа пересечения графов это книга по математике, минимальное количество краевых переходов необходимо в графические рисунки. Его написал Маркус Шефер, профессор компьютерных наук в Университет ДеПола и опубликованы в 2018 году издательством CRC Press в своей серии книг Дискретная математика и ее приложения.

Темы

Основной текст книги состоит из двух частей: о номере перекрестка в традиционном понимании и о вариантах номера перекрестка, за которыми следуют два приложения.[1] предоставление справочного материала по топологическая теория графов и теория сложности вычислений.[2]

После введения задачи в первой главе изучается число пересечений полные графики (включая Предполагаемая формула Хилла для этих номеров) и полные двудольные графы (Проблема кирпичного завода Турана и гипотеза числа перекрестков Заранкевича), что снова дает гипотетическую формулу).[2][3] Он также включает пересечение числового неравенства, а Теорема Ханани – Тутте по паритету переходов.[1] Вторая глава касается других специальных классов графов, включая графические продукты (особенно продукты графики цикла ) и графы гиперкуба.[2][3] После третьей главы, связывающей число пересечений с параметрами графика, включая перекос, ширина пополам, толщина, и (через Гипотеза Альбертсона ) хроматическое число, последняя глава части I посвящена вычислительная сложность поиска чертежей графа с минимальным пересечением, включая результаты, что проблема одновременно НП-полный и управляемый с фиксированными параметрами.[1][2][3]

Во второй части книги две главы посвящены числу прямолинейных пересечений, описывая рисунки графов, на которых ребра должны быть представлены в виде отрезков прямых линий, а не произвольных кривых, и Теорема Фари что каждый планарный граф таким образом можно нарисовать без пересечений. Другая глава касается 1-планарные графы и соответствующий местный номер перехода, наименьший номер k такой, что график может быть нарисован не более чем k переходов на край. Две главы касаются книжные вложения и строковые графики, и еще две главы посвящены вариациям числа пересечений, которые подсчитывают пересечения по-разному, например, по количеству пар ребер, которые пересекаются или пересекаются нечетное количество раз. Последняя глава части II касается удары и проблема поиска чертежей с максимальным количеством пересечений.[2][3]

Аудитория и прием

Книгу можно использовать как расширенный учебник, и для этого есть упражнения.[2][3] Однако предполагается, что его читатели уже знакомы с обоими теория графов а также дизайн и анализ алгоритмы.[2] Рецензируя книгу, Л. В. Бейнеке называет это «ценным вкладом» за представление многих результатов в этой области.

Рекомендации

  1. ^ а б c Ву, Baoyindureng, "Обзор Числа пересечения графов", zbMATH, Zbl  1388.05005
  2. ^ а б c d е ж грамм Дэйв, Маулик А. (март 2020 г.), "Обзор Числа пересечения графов", Обзоры MAA, Математическая ассоциация Америки
  3. ^ а б c d е Бейнеке, Лоуэлл (Апрель 2019 г.), "Обзор Числа пересечения графов", Американский математический ежемесячный журнал, 126 (4): 379–384, Дои:10.1080/00029890.2019.1567230