Улучшенные Приближенные Алгоритмы для Задачи Контактных Представлений
Michael A. Bekos, Thomas C. van Dijk, Martin Fink, Philipp Kindermann, Stephen Kobourov, Sergey Pupyrev, Joachim Spoerhase, and Alexander Wolff
Аннотация. Мы изучаем следующую геометрическую задачу: Для данного графа, вершины которого являются прямоугольники с фиксированными сторонами на плоскости, построить контактное представление так чтобы два прямоугольника касались тогда когда графе содержит соотвествующее ребро. Задача называется КОНТАКТНОЕ ПРЕДСТАВЛЕНИЕ СЕТЕЙ СЛОВ, так как она формализуеют геометрическую модель рисования семантического облака слов. Эиа задача, как известно, NP-трудна, и существуют алгоритмы аппроксимации для некоторых классов графов для версии оптимизации в которой каждый контакт имеет некоторый вес. Мы разработали первый O(1)-аппроксимационный алгоритм для общего случая задачи, когда на входе взвешенный граф. Так как подграф реализованных контактов обязательно планарный, мы также изучаем несколько планарных классов графов (а именно звезды, деревья, внешнепланарные и планарные графы), и улучшаем известные результаты. Для некоторых классов графов, мы также предлагаем усовершенствования в невесовом варианте, где каждый контакт имеет одинаковый вес. Наконец, мы показываем, что проблема является в APX-трудной для двудольных графов ограниченной максимальной степени.
