Вложение графа, которое максимизирует минимальный угол

13

Для данного плоского графа его можно вложить в линейное время, свободно переходя в сетку . Меня интересует, известны ли какие-либо эффективные алгоритмы, позволяющие прямой линии встраивать планарный граф, свободно пересекающийся в сетку n c × n c , для некоторого малого c , такого, чтобы минимальный угол между двумя ребрами был максимальным?N×NNс×Nсс

reference-request graph-theory graph-drawing Питер
источник
Я предполагаю, что вы заинтересованы в встраивании прямой линии. Иначе вопрос тривиален ...
Сариэль Хар-Пелед
да, меня интересуют вложения прямой линии
Питер

Ответы:

15

Я не думаю, что такой алгоритм известен. Известные мне результаты о максимизации минимального угла на прямых линиях плоских графиков:

  1. Каждый планарный график имеет (возможно, неплоский) рисунок, на котором минимальный угол обратно пропорционален максимальному градусу. Основную идею доказательства и некоторые ссылки см. По адресу http://11011110.livejournal.com/230133.html.

  2. О((журнал⁡d)/d3), Этот результат обусловлен Гаргом и Тамассией, «Планарные чертежи и угловое разрешение: алгоритмы и границы», ESA '94. Они также показывают, что для достижения почти оптимальных углов с помощью сетки может потребоваться сетка экспоненциальной площади.

  3. Каждый плоский график имеет плоский чертеж, в котором минимальный угол ограничен функцией его степени. Это можно показать с помощью теоремы об упаковке кругов Кобе-Андреева-Терстона. Ссылку на немного более строгую версию этого результата (показывающую, что у каждого плоского графа ограниченной степени есть планарный чертеж с ограниченным числом уклонов ребер) см. Http://11011110.livejournal.com/205447.html

Дэвид Эппштейн
источник
Этот ответ очень интересный, спасибо. Знаете ли вы, если что-то известно о проблеме, когда вы хотите встроить планарный график, свободно пересекающийся в сетку, где угол между любым ребром и осью х кратен некоторомуα и цель состоит в том, чтобы выбрать αкак можно больше?
Питер
Если вы еще не знаете, встраивание, оно завершено NP. В частности, трудно определить, будет ли работать α = π / 2. См. Garg and Tamassia, "О вычислительной сложности тестирования прямой и прямолинейной планарности", SIAM J. Comput. 2001.
Дэвид Эппштейн