검색 기능은 준비 중입니다.
검색 기능은 준비 중입니다.

The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice

The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice

Trade off between Page Number and Number of Edge-Crossings on the Spine of Book Embeddings of Graphs 그래프 책 임베딩의 척추에서 페이지 번호와 가장자리 교차 수 사이의 균형

Miki Shimabara MIYAUCHI

  • 조회수

    0

  • 이것을 인용

요약 :

이 논문은 다음의 문제를 연구한다. 책 삽입 그래프의. 각 가장자리가 하나로 표시되도록 허용되는 경우 또는 그 이상의 페이지 책등을 가로지르면 모든 그래프가 G 3페이지짜리 책에 삽입할 수 있습니다. 최근에는 3페이지 분량의 책이 삽입되어 있는 것으로 나타났습니다. G 각 가장자리가 척추를 교차하는 형태 O(로그2 n) 번. 이 논문에서는 3페이지가 넘는 책을 고려합니다. 이 경우 완전한 그래프가 나타나는 것으로 알려져 있습니다. Knn 정점은 n/2 -척추에 가장자리 교차가 없는 페이지 책입니다. 따라서 책 임베딩을 고안하는 것은 흥미로운 문제가 됩니다. G 사용되는 페이지 수와 척추의 가장자리 교차 수를 모두 줄이기 위해서입니다. 이 논문은 다음과 같은 존재가 있음을 보여줍니다. d-페이지 북 임베딩 G 각 가장자리가 척추를 교차하는 형태 O(로그d n) 번. 직접적인 결과로서 임의의 실수에 대해 s, 있습니다 ns -페이지 북 임베딩 G 각 가장자리가 척추를 일정한 횟수만큼 교차합니다. 다른 논문에서 Enomoto-Miyauchi-Ota는 정수에 대해 다음을 보여줍니다. d만약 n 에 비해 충분히 크다. d, 다음을 포함하려면 Knd-페이지 책, Ω(가 있어야 합니다.n2 기록d n) 가장자리가 척추 위로 교차하는 점입니다. 이는 우리의 결과가 다음에 대해 가능한 최고임을 의미합니다. Kn 이 경우

발행
IEICE TRANSACTIONS on Fundamentals Vol.E83-A No.8 pp.1732-1734
발행일
2000/08/25
공개일
온라인 ISSN
DOI
원고의 종류
LETTER
범주
그래프와 네트워크

작성자

키워드