그래프 예쁘게 그리기

최근 관계형 데이터 베이스 디자인 도구를 만들고 있는 데, DB로 부터 역공학 된 DB의 모델을 우아하게 그려주는 문제를 담당하게 되었다. 이들(테이블과 관계선들)을 보기 좋게 배치하는 데 필요한 여러가지 관심사가 있는 데, 그중에 하나가 교차선 없이 공간 효율적으로 테이블들과 관계를 배치하는 문제이다.

교차된 선이 나타나지 않게끔 버텍스를 이동하는 아이폰용 퍼즐게임을 즐겨본적이 있어서, 이와 관련된 AI나 그래프 이론이 있을거라 생각해서 뒤져봤다.

그러나 이런 문제에 대한 알고리즘 연구가 이정도로 형편없다는 데 매우 놀랄 수 밖에 없었다. 주제를 명기하는 이름조차 제대로 없어서, Drawing Graphs Nicely 정도로 적당히 불리고 있었다. 아무튼 다음과 같은 요구 조건들이 달성되야 한다.

1. 교차: 가능한한 교차되는 선이 나타나지 않아야 한다.
2. 영역: 가능한한 적은 면적을 사용하여 배치해야 한다.
3. 엣지 길이: 가능한한 엣지의 길이는 짧아야 하며, 장해물을 피해가야 한다.
4. 비율: 주어진 비율에 대해 최적화된 배치를 이뤄야 한다. (어느 용지에 출력할 것이냐 등등의 문제)

불행하게도 이 Goal들은 서로 배타적이지 못하고, 모순을 이루기도 한다. 더더군다나 교차등과 같은 문제는 NP 컴플릿 문제를 발생시키기도 한다.

수학적 연구가 제대로 진행되지 않은 탓에, 이것에 대해 최적해나, 성능 기반의 유사해를 내 놓는 접근 방식은 사용할 수 없을 것 같고 - 개발자로서는 도저히 이 무시무시한 시도를 엄두조차 낼 수 없다 - , 장력 시뮬레이션등과 같은 - 스프링 레이아웃과 같은 - 방법이나 뽕빨 휴리스틱을 써야 할 것 같다. 

30년간 아무런 진전도 보이지 못한 인공지능 분야의 몰락은 참 아쉬운 일이다. 에라이. 하긴 뭐 돈 안되니깐. 인정.