Если смягчить постановку планарного графа.

То мне было-бы достаточно рёбер которые красиво пересекаются. Ну тоесть не под острыми углами (2-5 градусов)
так чтобы их было видно. И чтоб вершины не накладывались как делает это GraphViz (circle,twopi).

И чтоб ребро красиво так огибало вершину. Как вода обтекает препятсвие. Я думаю тут уже нет комбинаторики.
Тут - численный метод. Бросил игральные кости на стол. Чутка подождал пока энергия системы не устаканится.
И вот - вуаля. Красивый граф.

Посмотрите как здесь Четверговый архивариус

Тут вопрос - как всегда в алгоритмах и структурах данных и API (язык запросов).

Разумеется на EAV можно как на глобус натянуть разные смыслы и положить в БД.

Но вот интерфейс программирования на таком EAV будет неудобен. Или у обычного SQL
разработчика дым из ушей пойдет когда вы попросите его найти все такие вершины
обладающие специфичным свойством. И перформанс такого запроса будет низким.
Ведь вам надо будет физически собирать данные разбросанные по разным частям
таблицы. Возможно для реляционных это удобно. Но граф (если в особенности
это semantic web), обладает очень гибкой схемой на которую невозможно
натянуть сет таблиц. Вот посмотрите из любопытсва на язык SPARQL и на то
какие смыслы в запросах. Вот этот язык изначально был заточен на графы.