- Логарифмическая граница для одновременного встраивания планарных графов (arXiv)
Автор : Рафаэль Штайнер
Аннотация: Множество G плоских графов с одинаковым числом n вершин называется одновременно вложимым, если существует множество P из n точек на плоскости такое, что каждый граф GεG допускает (беспересекательное) прямолинейное вложение с вершины расположены в точках P. Коллекция конфликтов представляет собой набор плоских графов одного порядка без одновременного встраивания. Хорошо известная открытая задача 2007 года, поставленная Брассом, Ченеком, Дунканом, Эфратом, Эртеном, Исмаилеску, Кобуровым, Любивом и Митчеллом, спрашивает, существует ли коллекция конфликтов размера 2. Хотя эта проблема остается широко открытой, мы даем краткое доказательство. что для достаточно большого n существует набор конфликтов, состоящий не более чем из (3+o(1))log2(n) плоских графов на n вершинах. Это значительно улучшает предыдущую экспоненциальную оценку O(n⋅4n/11) для той же задачи, которая была недавно установлена Гоенкой, Семнани и Йипом. Мы также даем безкомпьютерное доказательство существования коллекции конфликтов размером 30, улучшив ранее наименьшую известную коллекцию конфликтов размером 49, которая была найдена с помощью мощного компьютера.
2.Линейные макеты двудольных планарных графов (arXiv)
Автор: Генри Фёрстер, Майкл Кауфман, Лаура Меркер, Сергей Пупырев, Хризанти Рафтопулу.
Аннотация: Линейная компоновка графа G состоит из линейного порядка ≺ вершин и разделения ребер. Часть называется очередью (стеком), если никакие два ребра не вкладываются (пересекаются), то есть два ребра (v,w) и (x,y) с v≺x≺y≺w (v≺x≺w≺y ) не может находиться в одной очереди (стеке). Наиболее известные нижняя и верхняя границы количества очередей, необходимых для планарных графов, составляют 4 [Alam et al., Algorithmica 2020] и 42 [Bekos et al., Algorithmica 2022] соответственно. В то время как структуры очередей специальных классов планарных графов привлекли повышенное внимание после революционного результата [Dujmović et al., J. ACM 2020], значимый класс двудольных плоских графов до сих пор оставался неуловимым, о чем явно просили Бекос и др. . В этой статье мы исследуем двудольные плоские графы и даем улучшенную верхнюю оценку, равную 28, путем усовершенствования существующих методов. Напротив, мы показываем, что двух очередей или одной очереди вместе с одним стеком недостаточно; последний отвечает на открытый вопрос Пупырева [ГД 2018]. Мы далее исследуем подклассы двудольных плоских графов и даем улучшенные верхние оценки; в частности, мы строим 5-очередные макеты для 2-вырожденных четырехугольников
