Кластерная планарность
При рисовании графов кластеризованный планарный граф представляет собой граф с иерархической кластеризацией его вершин, так что граф можно нарисовать вместе с набором простых замкнутых кривых, окружающих каждый кластер, без пересечений между ребрами или кластерами графа. [1]
Кластеризацию можно описать комбинаторно набором подмножеств вершин, таких, что для каждых двух подмножеств либо оба не пересекаются, либо одно содержится в другом. Не требуется, чтобы кластеризация была максимальной или чтобы каждая вершина принадлежала кластеру.В кластеризованном плоском рисунке никакие два ребра не могут пересекать друг друга (то есть граф должен быть плоским ), никакие две кривые, представляющие кластеры, не могут пересекать друг друга, ребро может пересекать границу кластера только в том случае, если оно соединяет вершину внутри кластера к вершине вне кластера, и когда ребро и граница кластера пересекаются, они могут пересечься только один раз. [1] После долгих прошлых работ над этой проблемой Радослав Фулек и Чаба Тот в 2019 году нашли алгоритм проверки кластерной планарности с полиномиальным временем. [2]
Ссылки
[ редактировать ]- ^ Jump up to: а б Кортезе, Пьер Франческо; Ди Баттиста, Джузеппе (2005), «Кластерная планарность», Proc. 21-й симп. Вычислительная геометрия (SCG'05) , Нью-Йорк: ACM, стр. 32–34, doi : 10.1145/1064092.1064093 , MR 2460345 . Краткий обзорный документ, связанный с приглашенным докладом в SCG.
- ^ Фулек, Радослав; Тот, Чаба Д. (2020), «Атомная вложимость, кластерная планарность и сгущаемость», Proc. 31-й симпозиум ACM-SIAM по дискретным алгоритмам , стр. 2876–2895, arXiv : 1907.13086 , doi : 10.1137/1.9781611975994.175