Most common and maybe the biggest limitation of graph layout algorithms today is their lack of incremental-layout ability. Whenever there is a change in the graph, these algorithms makes no references to current layout informations and whole layouting procedures is repeated again. This problem magnifies as informations to represent get large or the algorithm is used in interactive environment where frequent user-interactions occurs, where the changes in the graph caused by user interactions are relatively small to overall size of the graph representing relationship between informations.
This thesis introduce an incremental graph layouting algorithm, variant of Sugiyama's algorithm, that reduces layouting computations by generating fewer dummy vertices, having better vertex ordering functions, and most importantly the incremental layout ability which drastically reduces the layouting time.
본 논문에서는 대화식 환경에서 증가적 그래프 배치 알고리듬에 관한 연구를 하였다. 기존배치 알고리듬의 가장 큰 단점은 증가적으로 변화에 대치하지 못하고 있는 점이다. 즉 현그래프에 작은 변화에도 기존 알고리듬은 현 배치 정보를 전혀 사용 하지 않고 배치 알고리듬을 재수행 한다. 이러한 시간적, 정보적 낭비는 표현하는 그래프의 크기가 크거나 사용자와 시스템간의 많은 통신이 있는 대화식 환경에서 극히 심해진다.
본 논문에서는 수기야마 알고리듬의 변형인 새로운 증가적 배치 알고리듬을 소개한다. 실험, 분석 결과 본 논문의 알고리듬이 기존 배치 방식보다 효율적임을 보인다.