평면 트리의 레벨 도시와 수직도시 알고리즘 = Algorithms for Level Drawing and Orthogonal Drawing in Planar Trees
저자
발행사항
서울 : 德成女子大學校 一般大學院, 2001
학위논문사항
학위논문(석사)-- 德成女子大學校 一般大學院: 電算 및 精補通信學科 2001
발행연도
2001
작성언어
한국어
주제어
KDC
004.76 판사항(4)
발행국(도시)
서울
형태사항
47p. ; 26cm.
소장기관
그래프 도시는 추상적인 구조체인 그래프를 시각화하여 2차원 평면상에 그려주는 작업이다. 좋은 그래프 도시란 판독성을 증가시켜서 그래프의 구조를 쉽게 파악할 수 있도록 한다. 판독성 문제는 미적 기준에 의해서 표현되며, 그래프 도시의 종류에 따라 다양한 미적 기준이 존재한다. 그러나 가장 일반적인 미적기준으로는 교차와 굴곡점 수의 최소화와 도시 면적의 최소화가 있다.
본 논문에서는 평면 트리에 대한 레벨 도시와 수직 상향/하향 도시 알고리즘을 제안한다.
트리는 실세계의 모델을 가시적으로 알기 쉽게 표현하기 위한 자료구조로서 자주 이용되어진다. 따라서 트리의 이해도와 판독성을 증가시켜 정보의 의미를 명확하게 전달하는 것은 매우 중요하다.
평면 트리에 대한 레벨 도시 알고리즘은 면적의 최소화와, 공간과 시각적 측면을 고려하여 적절한 정점의 위치 배정을 고려해야 한다. Tilford는 최소면적의 공간에 트리를 보기좋게 도시하는 알고리즘을 제시하였는데, 이는 트리의 전체적 구조가 왼쪽으로 치우칠 뿐 아니라, 도시시에 노드의 불필요한 이동이 많이 일어나는 등의 단점을 가지고 있다. 본 논문에서는 이러한 단점을 개선한 레벨 도시
하는 알고리즘을 제시한다. 트리가 n 개의 정점들로 이루어졌을 때, 레벨 도시 알고리즘은 O(n²)면적에 도시된다.
평면 트리에 대한 수직 상향/하향 도시 알고리즘은 굴곡점 수의 최소화와 면적의 최소화를 고려해야 한다. Tamassia의 수직 도시 알고리즘은 트리가 n 개의 정점들로 이루어졌을 때, 최소 면적 O(n log log n)영역에 O(n)의 굴곡점을 가지고 도시된다. 본 논문에서 제안하는 수직 상향/하향 도시 알고리즘은 최소 면적인 O(n log log n)영역에 굴곡점이 없이 도시한다.
A graph is an abstract structure, and a graph drawing draws such graphs in a plane. Various graphic standards are used for drawing graphs. The usefilness of a graph drawing depends on its readability, that is, the capability of conveying the meaning of the graph quickly and clearly. Readability issues can be expressed by means of aesthetics criteria, such as minimization of the number of bends and crossings, and the area of the drawing.
We suggest algorithms for level and orthogonal drawing in a planar tree.
A tree often is used as an abstract structure, and it is drawn in a plane for taking a high readability. It is important to convey the meaning of the graph quickly and clearly.
A level drawing issues can be expressed by means of assign proper vertex positions in consideration of the space and visual angle. Tilford suggests a level drawing algorithm with optimal area in a planar tree, but it has two problems, unbalance tree leaning to the west, and unnecessary reassignment. We suggest an improved algorithm without these problems. If a tree consists of n vertex, it is drawn with O(n²) area by our algorithm for level drawing.
A orthogonal drawing issues can be expressed by minimization of the number of bends and the area of the drawing. Tamassia suggests a orthogonal drawing algorithm with O(n log log n) area and O(n) bends in a planar tree. We suggest an improved algorithm with O((n log log n) area and no bend by our algorithm for orthogonal drawing.
서지정보 내보내기(Export)
닫기소장기관 정보
닫기권호소장정보
닫기오류접수
닫기오류 접수 확인
닫기음성서비스 신청
닫기음성서비스 신청 확인
닫기이용약관
닫기학술연구정보서비스 이용약관 (2017년 1월 1일 ~ 현재 적용)
학술연구정보서비스(이하 RISS)는 정보주체의 자유와 권리 보호를 위해 「개인정보 보호법」 및 관계 법령이 정한 바를 준수하여, 적법하게 개인정보를 처리하고 안전하게 관리하고 있습니다. 이에 「개인정보 보호법」 제30조에 따라 정보주체에게 개인정보 처리에 관한 절차 및 기준을 안내하고, 이와 관련한 고충을 신속하고 원활하게 처리할 수 있도록 하기 위하여 다음과 같이 개인정보 처리방침을 수립·공개합니다.
주요 개인정보 처리 표시(라벨링)
목 차
3년
또는 회원탈퇴시까지5년
(「전자상거래 등에서의 소비자보호에 관한3년
(「전자상거래 등에서의 소비자보호에 관한2년
이상(개인정보보호위원회 : 개인정보의 안전성 확보조치 기준)개인정보파일의 명칭 | 운영근거 / 처리목적 | 개인정보파일에 기록되는 개인정보의 항목 | 보유기간 | |
---|---|---|---|---|
학술연구정보서비스 이용자 가입정보 파일 | 한국교육학술정보원법 | 필수 | ID, 비밀번호, 성명, 생년월일, 신분(직업구분), 이메일, 소속분야, 웹진메일 수신동의 여부 | 3년 또는 탈퇴시 |
선택 | 소속기관명, 소속도서관명, 학과/부서명, 학번/직원번호, 휴대전화, 주소 |
구분 | 담당자 | 연락처 |
---|---|---|
KERIS 개인정보 보호책임자 | 정보보호본부 김태우 | - 이메일 : lsy@keris.or.kr - 전화번호 : 053-714-0439 - 팩스번호 : 053-714-0195 |
KERIS 개인정보 보호담당자 | 개인정보보호부 이상엽 | |
RISS 개인정보 보호책임자 | 대학학술본부 장금연 | - 이메일 : giltizen@keris.or.kr - 전화번호 : 053-714-0149 - 팩스번호 : 053-714-0194 |
RISS 개인정보 보호담당자 | 학술진흥부 길원진 |
자동로그아웃 안내
닫기인증오류 안내
닫기귀하께서는 휴면계정 전환 후 1년동안 회원정보 수집 및 이용에 대한
재동의를 하지 않으신 관계로 개인정보가 삭제되었습니다.
(참조 : RISS 이용약관 및 개인정보처리방침)
신규회원으로 가입하여 이용 부탁 드리며, 추가 문의는 고객센터로 연락 바랍니다.
- 기존 아이디 재사용 불가
휴면계정 안내
RISS는 [표준개인정보 보호지침]에 따라 2년을 주기로 개인정보 수집·이용에 관하여 (재)동의를 받고 있으며, (재)동의를 하지 않을 경우, 휴면계정으로 전환됩니다.
(※ 휴면계정은 원문이용 및 복사/대출 서비스를 이용할 수 없습니다.)
휴면계정으로 전환된 후 1년간 회원정보 수집·이용에 대한 재동의를 하지 않을 경우, RISS에서 자동탈퇴 및 개인정보가 삭제처리 됩니다.
고객센터 1599-3122
ARS번호+1번(회원가입 및 정보수정)