Генерируйте большой случайный плоский график
Что самый эффективный путь состоит в том, чтобы генерировать большое (~ 300k вершины), случайный плоский график ("случайный" здесь означает равномерно распределенный)?
1 ответ
Ну, одним из методов может быть попытка сгенерировать случайный граф, который удовлетворяет ограничениям, аналогичным ограничениям планарного графа (например, ребра <= 3*вершины - 6) и проверить, является ли он планарным за время O(n), используя алгоритм тестирования планарности Тарджана. Если он не является планарным, сгенерируйте его снова. Не уверен, насколько это будет эффективно для 300K вершин (и будет ли это вообще давать графы с равномерной вероятностью).
Есть некоторая литература по генерации планарных графов, я нашел одну работу здесь: Generating Labeled Planar Graphs, которая, очевидно, имеет ожидаемое время работы O(n^4), и, возможно, тоже не стоит того. Возможно, приведенные там ссылки помогут вам найти что-то, что может помочь.
Удачи!