Кластерная планарность - Clustered planarity

Сгруппированный планарный рисунок

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

Кластеризация может быть описана комбинаторно набором подмножеств вершин так, что для каждых двух подмножеств либо оба не пересекаются, либо одно содержится в другом. Не требуется, чтобы кластеризация была максимальной и каждая вершина принадлежала кластеру. В кластерном плоском чертеже никакие два ребра не могут пересекать друг друга (то есть граф должен быть планарный ), никакие две кривые, представляющие кластеры, не могут пересекать друг друга, ребро может пересекать границу кластера только в том случае, если оно соединяет вершину внутри кластера с вершиной вне кластера, и когда граница ребра и граница кластера пересекаются, они могут пересекаться только один раз. .[1] После долгой прошлой работы над этой проблемой в 2019 году Радослав Фулек и Чаба Тот нашли алгоритм полиномиального времени, проверяющий кластерную планарность.[2]

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

  1. ^ а б Кортезе, Пьер Франческо; Ди Баттиста, Джузеппе (2005), «Кластерная планарность», Proc. 21-й симп. Вычислительная геометрия (SCG'05), Нью-Йорк: ACM, стр. 32–34, Дои:10.1145/1064092.1064093, МИСТЕР  2460345. Краткий обзорный документ, связанный с приглашенным докладом в SCG.
  2. ^ Фулек, Радослав; Тот, Чаба Д. (2020), «Встраиваемость атомов, кластерная планарность и утолщаемость», Появиться в Proc. 31-й симпозиум ACM-SIAM по дискретным алгоритмам, arXiv:1907.13086