This is a good article. Click here for more information.

북 임베딩

Book embedding
3페이지 분량의 책에는5 전체 그래프K가 수록되어 있다.평면 그래프가 아니기 때문에 더 적은 페이지에 교차하지 않으면 이 그래프를 삽입할 수 없기 때문에 책의 두께는 3이다.

그래프 이론에서 책 임베딩은 책에 삽입하기 위해 그래프를 평면 임베딩하는 것을 일반화하는 것으로, 모든 반플레인이 경계와 같은 선을 가지고 있다.일반적으로 그래프의 정점은 척추라고 불리는 이 경계선에 놓여 있어야 하며, 가장자리는 단일 반평면 내에 있어야 한다.그래프의 책 두께는 그래프를 포함한 어떤 책에도 가능한 최소의 반평면이다.책 두께는 페이지넘버, 스택넘버 또는 고정외선염이라고도 한다.책 임베딩은 또한 페이지 너비와 책 교차 번호를 포함한 몇 가지 다른 그래프 불변제를 정의하는데 사용되었다.

정점이 없는 모든 그래프는 책 두께가 최대 n / {\이며,이 공식은 완전한 그래프를 위한 정확한 책 두께를 제공한다책 두께가 1인 그래프는 외부 평면 그래프다.책 두께가 최대 2개인 그래프는 해밀턴 하위 그래프인데, 이것은 항상 평면형이다. 보다 일반적으로 모든 평면 그래프는 책 두께가 최대 4개다.모든 마이너 폐쇄 그래프 패밀리, 특히 경계 트리 너비 또는 경계 속(bounded treewidth)이 있는 그래프도 경계 책 두께를 가지고 있다.책 척추에 따라 고정된 꼭지점 순서를 알고 있거나 모르고 주어진 그래프의 정확한 책 두께를 결정하는 것은 NP 하드다.내장의 척추를 따라 정점을 일정한 순서로 배열하여 그래프를 포함하는 3페이지 분량의 책의 존재 여부를 시험하는 것은 알 수 없는 계산 복잡성을 가지고 있다. 다항 시간에는 해결할 수 있는 것도 아니고 NP-하드라고도 알려져 있지 않다.

책 임베딩 연구를 위한 최초의 동기 중 하나는 VLSI 설계에 응용 프로그램을 포함했는데, VLSI 설계에서는 책 임베딩의 정점이 회로의 구성요소를 나타내고 와이어는 그 사이의 연결을 나타낸다.북 임베딩은 그래프 도면에 응용 프로그램도 있는데, 여기서 두 가지 표준 시각화 스타일 중 두 가지를 북 임베딩으로 구성할 수 있다.

운송 계획에서, 교통 신호등에서 만나고 상호작용하는 다양한 발과 차량 교통의 출처와 목적지는 서로 다른 소스-대상 쌍을 연결하는 가장자리가 있는 그래프의 정점으로 수학적으로 모델링될 수 있다.이 그래프를 포함한 책자는 가능한 한 적은 신호 단계로 모든 트래픽이 교차로를 가로질러 이동할 수 있는 스케줄을 설계하는 데 사용될 수 있다.RNA의 접이식 구조와 관련된 생물정보학 문제에서 단면책 임베딩은 고전적인 형태의 핵산 이차 구조를 나타내며, 2면책 임베딩은 유사성을 나타낸다.책 임베딩의 다른 응용으로는 추상대수와 매듭 이론이 있다.

역사

위상학적 공간으로서의 책의 개념은 C에 의해 정의되었다.A. Persinger와 Gail Atneosen은 1960년대.[1][2]이 작업의 일환으로, 아트네오센은 이미 책에 그래프를 삽입하는 것을 고려했다.그가 연구한 임베딩은 그래프를 다른 위상학적 공간에 삽입하는 것과 같은 정의를 사용했는데, 정점은 구별되는 점으로 표현되고, 가장자리는 곡선으로 표현되며, 두 가장자리가 교차할 수 있는 유일한 방법은 공통의 끝점에서 만나는 것이다.

1970년대 초, 폴 C. 카이넨과 L.테일러 올만은 대부분의 후속 연구에 사용하게 된 보다 제한적인 형태의 임베딩을 개발했다.그래프의 정점은 책의 척추를 따라 배치되어야 하며 각 가장자리는 한 페이지에 놓여야 한다.[3][4]책 임베딩의 후기 개발에서 중요한 이정표에는 1980년대 후반에 미할리스 얀나카키스가 평면 그래프의 책 두께가 최대 4개라는 [5][6]증거와 1990년대 후반에 책 임베딩과 생물정보학 사이에 밀접한 관계가 있다는 발견이 있다.[7]

정의들

유틸리티 graphK는3,3 2쪽짜리 책 임베딩이 없지만, 건널목 하나만 있는 2쪽짜리 책처럼 그릴 수 있다.따라서, 그것의 2페이지의 책 교차번호는 1이다.
이 다이아몬드 그래프의 1페이지짜리 내장에는 페이지 너비 3이 있는데, 노란색 광선이 세 개의 가장자리를 가로지르기 때문이다.

책은 특정한 종류의 위상학적 공간이며, 반평면의 부채라고도 불린다.[1][8]책의 척추나 뒷면이라 불리는 한 줄 ℓ과 책의 페이지나 잎사귀라고 불리는 하나 이상의 반플레인의 모음으로 구성되어 있으며,[9] 각각은 척추를 경계로 하고 있다.페이지 수가 유한한 책은 예를 들어 cart을 데카르트 좌표계의 z축으로 선택하고, xz 평면에 대한 이음각은 2㎛/k의 정수배수인 k 하프플레인으로 선택함으로써 3차원 공간에 삽입할 수 있다.[10]

책 B에 유한 그래프 G를 그린 도면은 B에 G의 모든 꼭지점이 B의 척추에 점으로 그려지고 G의 모든 가장자리가 B의 한 페이지 안에 있는 곡선으로 그려지도록 한 것이다.K-page book crossing number of G는 k-page book drawing에 있는 최소 교차 수입니다.[11]

B에 G를 내장한 서적은 B에 G를 내장한 그래프를 구성하는 서화다.즉, 가장자리 교차점이 없는 B에 G를 그린 책 그림이다.모든 유한 그래프에는 충분한 수의 페이지가 있는 책 위에 책이 박혀 있다.예를 들어, 그래프의 각 가장자리를 항상 별도의 페이지에 삽입할 수 있다.책 두께, 페이지 번호 또는 G의 스택 번호는 G가 포함된 책을 포함하는데 필요한 최소 페이지 수입니다. 책 포함의 품질을 측정하는 또 다른 매개변수는 페이지 너비다.이것은 한 페이지 내에서 척추에 수직인 광선으로 교차할 수 있는 최대 가장자리 수입니다.동등하게(각 가장자리가 단조로운 곡선으로 그려지는 책 임베딩의 경우), 가장자리의 끝점 쌍에 의해 척추에 정의된 구간이 모두 교차하도록 한 페이지 내의 가장자리 부분 집합의 최대 크기다.[12][13][14]

이러한 정의에 있어서 가장자리는 책의 한 페이지 안에만 머물도록 허용된다.아트네오센은 이미 관찰한 바와 같이, 만약 가장자리가 책의 척추에 걸쳐 한 페이지에서 다른 페이지로 넘어갈 수 있다면, 모든 그래프는 세 페이지짜리 책에 삽입될 수 있다.[15][2][16]척추 교차가 허용되는 3페이지의 위상학 책을 위해, 모든 그래프에는 최대 에지당 로그 수의 척추 교차가 포함될 수 있으며,[15] 어떤 그래프는 이 많은 척추 교차가 필요하다.[17]

특정 그래프

첫 번째 그림에서 보듯이 전체5 그래프 K의 책 두께는 세 가지인데, 비 평면 그래프로서 책 두께는 두 개보다 크지만, 세 페이지가 포함된 책이 존재한다.보다 일반적으로, n ≥ 4 정점을 가진 모든 전체 그래프의 책 두께는 정확히 n/ 이다 이 결과는 또한 n-vertex 그래프의 가능한 최대 책 두께에 상한을 부여한다.[10]

전체 그래프 K의n 2페이지 교차번호는

앤서니 힐에 대한 아직 증명되지 않은 추측과 이 그래프의 제한되지 않은 교차점 수를 일치시킨다.즉 힐의 추측이 맞다면 교차 횟수를 최소화하는 이 그래프의 도면은 2페이지짜리 도면이 된다.[18]

전체 초당적 그래프 K의a,b 책 두께는 최대 min(a,b)이다.이 책 두께로 도면을 구성하려면, 각 꼭지점에 대해 초당파의 작은 면에 있는 가장자리 부분을 자신의 페이지에 배치할 수 있다.예를 들어, K는4,4 책 두께가 4가 아니라 3이다.그러나 그래프의 양면이 b > a(a - 1)로 매우 불균형할 때 K의a,b 책 두께는 정확히 a가 된다.[10][19]

Turan 그래프 T(kr,r)의 경우(독립 세트당 k 정점의 r 독립된 집합으로 구성된 완전한 다중 사이트 그래프 K는k,k,... 서로 다른 독립 세트로부터 두 정점 사이의 에지를 가지고 있다) 책 두께 t는 사이에 샌드위치된다.

그리고 r이 홀수일 때 상한은 다음과 같이 개선될 수 있다.

[10][20]

2진수 de Bruijn 그래프, shuffle-change 그래프, 큐브 연결 주기(이 그래프들이 평면이 아닐 정도로 충분히 큰 경우)의 책 두께는 정확히 3이다.[21]

특성.

평면성과 외형성

골드너-하라리 그래프, 책의 두께가 3인 평면 그래프

주어진 그래프 G의 책 두께는 G가 외부 평면 그래프인 경우에만 최대 1이다.외부 평면 그래프는 모든 정점이 내장의 외부 면에 속하는 평면 내장을 갖는 그래프다.그러한 그래프의 경우, 정점을 바깥 면에 나타나는 것과 동일한 순서로 배치하면, 주어진 그래프를 포함하는 1페이지의 책을 제공한다.(그래프의 굴절점은 반드시 바깥 면 주위의 정점의 주기적 순서에 두 번 이상 나타나지만, 그 사본들 중 하나만 포함되어야 한다.책 임베딩)반대로, 한 페이지 분량의 책 임베딩은 자동적으로 외부 평면 임베딩이다.왜냐하면, 그래프가 한 페이지에 내장되어 있고, 또 다른 반평면이 척추에 부착되어 페이지를 완전한 평면으로 확장한다면, 임베딩의 바깥 면은 추가된 반평면 전체를 포함하며, 모든 정점은 이 바깥 면에 놓여 있다.[10][12]

두 페이지 분량의 책 임베딩은 모두 평면 임베딩의 특별한 경우인데, 두 페이지의 결합은 평면 전체와 토폴로지가 동일한 공간이기 때문이다.따라서 책 두께가 2인 모든 그래프는 자동으로 평면 그래프가 된다.좀 더 정확히 말하면, G가 해밀턴 사이클이 있는 평면 그래프의 하위 그래프일 경우에만 그래프 G의 책 두께는 최대 2이다.[10]그래프에 2페이지 임베딩이 주어질 경우, 이미 인접하지 않은 척추를 따라 두 개의 연속 정점 사이에 여분의 에지를 추가(모든 페이지에)하고 첫 번째와 마지막 척추 정점 사이에 추가함으로써 평면 해밀턴 그래프에 증강할 수 있다.Goldner-Harary 그래프는 책 두께가 없는 평면 그래프의 예를 제공한다. 2는 최대 평면 그래프이므로 평면성을 보존하면서 에지를 추가할 수 없으며, 해밀턴 사이클도 없다.[10]해밀턴 사이클에 의한 이러한 특성화 때문에, 2페이지 분량의 책 임베딩이 있는 그래프는 해밀턴 이하의 그래프로도 알려져 있다.[12]

최대 등급이 4인 모든 평면 그래프는 최대 2개의 책 두께를 가진다.[22]평면 3-트리는 책 두께가 최대 3이다.[23]보다 일반적으로 모든 평면 그래프는 책 두께 4를 가진다.[5][6][24]책[6] 두께가 정확히 4개인 평면 그래프가 존재한다는 것은 1986년 미할리스 얀나카키스에 의해 주장되어 왔다.그러나 후속 저널 논문에 발표된 이 주장에 대한 자세한 증거는 2020년에야 알 수 있었는데,[5][24] 당시 베코스 외는 어떤 책 임베딩에도 4페이지가 필요한 나무 너비 4의 평면 그래프를 제시하였다.

하위 영역에서의 동작

다이아몬드 그래프의 책 두께는 가장자리 분할 후 증가한다.

각 가장자리 내에 새로운 정점을 추가하여 그래프의 모든 가장자리를 두 개의 가장자리 경로로 세분화하면 때때로 책 두께가 증가할 수 있다.예를 들어, 다이아몬드 그래프는 책 두께 1(외측 평면도)을 가지고 있지만, 그 하위 분할은 책 두께 2(평면도와 하위 해밀턴이지만 외부 평면도는 아니다)를 가지고 있다.그러나 이러한 세분화 과정은 때로는 세분화된 그래프의 책 두께를 현저히 줄일 수 있다.예를 들어, 완전 그래프 Kn의 책 두께 vertices의 숫자에 나섰으나,two-edge 길로 각각의 가장자리의 분획 구분의 책 두께 훨씬 작은 하위 구분을 생산함에 비례합니다만 O이 Blankenship &, Op과 같은 예들의 존재에도 불구하고{O({\sqrt{n}})\displaystyle}.[25](n).orowski(iii) 분절의 책 두께가 원래 그래프의 책 두께보다 너무 작을 수 없다고 추측했다.구체적으로, 그들은 모든 그래프 G와 G의 모든 가장자리를 2-엣지 경로로 대체하여 형성된 그래프 H에 대해 H의 책 두께가 t이면 G의 책 두께가 최대 f(t)가 되는 함수 f가 존재한다고 추측했다.[16]그들의 추측은 거짓으로 드러났다: 별과 삼각형 기울기로 이루어진 데카르트 산물에 의해 형성된 그래프는 한없는 책 두께를 가지고 있지만, 그들의 가장자리를 6개의 가장자리로 나누면 책 두께가 3개로 줄어든다.[26]

다른 그래프 불변제와의 관계

책 두께는 주어진 그래프의 가장자리를 덮는 데 필요한 평면 그래프의 수인 두께와 관련이 있다.그래프 G는 평면에서 그릴 수 있는 경우 두께가 θ이고, 가장자리는 θ 색으로 채색하여 서로 같은 색의 가장자리가 교차하지 않도록 한다.이와 유사하게, 그래프 G는 반평면의 경계에 정점이 있는 반평면에 그릴 수 있는 경우 책 두께 θ이 있고, 가장자리는 같은 색상의 두 가장자리 사이에 교차하지 않는 θ 색상으로 채색된다.이 책 두께의 공식에서, 가장자리의 색상은 책 임베딩의 페이지에 해당한다.그러나 두께와 책의 두께는 서로 매우 다를 수 있다: 두께가 두 개임에도 불구하고 [25][15][16]한없는 책 두께를 가진 그래프(완전한 그래프의 부분 부분)가 존재한다.[25]

treewidth k의 그래프는 경향을 보여 대부분의 k+1[27][28]에 바운드 k>를 위한 철저한 것;2책 두께.m모서리가[27]그래프는 경향(m){O({\sqrt{m}})\displaystyle},[29]과 속 g의 그래프{O({\sqrt{g}})\displaystyle}.[30]더 일반적으로(g), 모든minor-closed 그래프 가족 thickn 책을 경계했다 책 두께 O이 책 두께 O고 있다.ess.[31][32] 한편 미성년자 이하에서는 닫히지 않는 1평형 그래프도 경계 [31]책 두께가 있지만 [33]K를2,2,2,2 포함한 일부 1평형 그래프는 책 두께가 최소 4개 이상이다.[34]

경계 책 두께의 그래프의 모든 얕은 부차는 희박한 그래프인데, 가장자리 대 정점의 비율은 부재의 깊이와 책 두께에만 의존하는 상수에 의해 경계된다.즉, 네셰틸 & 오소나 데 멘데스(2012년)의 용어에서 경계 서적 두께의 그래프는 확장에 경계를 두었다.[31]그러나 경계 확장보다 훨씬 강력한 요구 조건인 경계 수준의 그래프도 한없는 책 두께를 가질 수 있다.[35]

책 두께 2의 그래프는 평면 그래프이기 때문에 평면 분리기 정리를 따른다. 분리기는 분리기, 정점 부분 집합이 있으며 분리기에는 ( n) {\ 정점만 있고, 분리기에는 정점만 있다.여기서 n은 그래프의 정점 수를 가리킨다.그러나 책 두께 3의 그래프는 하위 선형의 구분자를 가지고 있지 않다.[36]

책 임베딩의 한 페이지 내의 가장자리는 스택 데이터 구조와 같은 어떤 방식으로 작용한다.이것은 스택에 대한 푸시 및 팝 연산의 임의적인 순서를 고려하고, 스택 연산이 책 임베딩의 척추를 따라 순차적으로 배치된 그래프의 정점에 해당하는 그래프를 형성함으로써 공식화될 수 있다.그런 다음 스택에서 객체 x를 튀기는 각각의 팝 작업에서 x를 밀어넣은 이전의 푸시 작업까지 에지를 그리면 결과 그래프는 자동으로 1페이지 임베딩이 된다.이러한 이유로, 그래프의 페이지 번호는 스택 번호라고도 불린다.같은 방법으로, 큐 데이터 구조의 임의적인 enqueue 및 dequeue 연산 순서를 고려할 수 있으며, 이러한 연산들을 정점으로 하여 한 페이지의 척추에 순서대로 배치하고 각 enque 연산과 해당 dequeue 연산 사이에 엣지가 있는 그래프를 형성할 수 있다.그런 다음 이 그래프에서 각 두 가장자리는 척추의 절개 간격을 교차시키거나 덮는다.유추에 의해, 연구자들은 그래프를 포함하는 큐를 위상학 책자에 내장하여 각 꼭지점이 척추에 놓여 있고, 각 가장자리는 한 페이지에 놓여 있으며, 각 두 가장자리는 동일한 페이지에 있는 척추의 교차 또는 커버 분리 간격을 포함하도록 정의했다.그래프를 포함하는 큐에 필요한 최소 페이지 수를 큐 번호라고 한다.[31][37][38]

계산 복잡성

원의 화음에 대한 교차 그래프인 원 그래프.정점 순서가 정해진 책 임베딩의 경우 책 두께를 찾는 것은 파생된 원 그래프를 색칠하는 것과 같다.

그래프의 책 두께를 찾는 것은 NP-hard이다.이것은 최대 평면 그래프에서 해밀턴의 주기를 찾는 것이 NP-완전하다는 사실에 따른 것이다.최대 평면 그래프에서 책 두께는 해밀턴 사이클이 존재하는 경우에만 2이다.따라서 주어진 최대 평면 그래프의 책 두께가 2인지 여부를 검정하는 것도 NP 완성이다.[39]

내장의 척추를 따라 그래프의 정점 순서가 고정된 경우, 주어진 그래프를 척추 순서에서 정점을 연결하는 주기로 증가시킴으로써 형성된 그래프의 평면성 검사의 한 예로서 선형적으로 두 페이지 임베딩(있는 경우)을 찾을 수 있다.[7]운거(1992)는 척추 순서가 고정된 3쪽짜리 임베딩도 다항식 시간에 찾을 수 있다고 주장했지만, 이 결과에 대한 그의 기록은 많은 세부사항을 생략하고 있다.[40]단, 4페이지 이상이 필요한 그래프의 경우, 원의 화음의 교차 그래프인 컬러링 서클 그래프의 NP-하드 문제와 동등하게, 가능한 최소 페이지 수로 임베딩을 찾는 문제는 NP-하드 상태로 남아 있다.고정된 척추 순서가 있는 그래프 G가 그 정점에 대해 주어진다면, 이러한 정점을 원을 중심으로 같은 순서로 그리고 선 세그먼트로 G의 가장자리를 그리면 G를 나타내는 화음의 집합이 생성된다.그러면 이 도표의 화음을 정점으로 하고 화음의 교차 쌍을 가장자리로 하는 원 그래프를 만들 수 있다.원 그래프의 색상은 G의 가장자리가 한 페이지에 교차하지 않고 그릴 수 있는 부분 집합으로 분할된 것을 나타낸다.따라서 최적의 색상은 최적의 책 임베딩과 같다.네 가지 이상의 색상으로 된 원 그래프 색상은 NP-하드(NP-hard)이고, 어떤 책 임베딩 문제에서 어떤 원 그래프가 이런 식으로 형성될 수 있기 때문에 최적의 책 임베딩도 NP-하드(NP-hard)라는 것이 뒤따른다.[41][42][43]2페이지 분량의 책 도면의 척추에 고정 정점 순서가 있는 경우, 이 숫자가 0이 아닐 때 교차 횟수를 최소화하는 것도 NP 하드다.[42]

척추 순서는 알 수 없지만 가장자리 부분을 두 페이지로 분할한 경우 SPQR 트리를 기반으로 한 알고리즘에 의해 선형적으로 2페이지 임베딩(있는 경우)을 찾을 수 있다.[44][45]그러나 척추 순서나 가장자리 파티션을 알 수 없을 때 2페이지의 임베딩을 찾는 것은 NP-완전이다.그래프의 책 교차 번호를 찾는 것도 NP-완전성 때문에 NP-완전성 때문에 2페이지 교차 번호가 0인지 여부를 테스트하는 특수 사례에 해당하기 때문이다.

경계가 확장된 결과, 경계가 있는 크기의 패턴 그래프가 더 큰 그래프의 하위 그래프로 존재하는지 여부를 알아내는 서브그래프 이형성 문제는 큰 그래프에 경계가 있는 책 두께가 있을 때 선형적으로 해결할 수 있다.패턴 그래프가 큰 그래프의 유도 하위 그래프인지, 큰 그래프에 대한 그래프 동형성이 있는지 탐지하는 경우에도 마찬가지다.[46][47]같은 이유로, 경계 책 두께의 그래프가 첫 번째 순서 논리학의 주어진 공식에 부합하는지 여부를 검정하는 문제는 고정 매개변수 추적 가능하다.[48]

Bekos, Kaufmann & Zielke(2015)는 문제를 Boolean 만족도 문제의 한 예로 변환하고 그 결과 문제에 SAT 해결기를 적용함으로써 최적의 책 임베딩을 찾는 시스템을 설명한다.그들은 그들의 시스템이 약 20분 안에 400Vx의 최대 평면 그래프를 위한 최적의 내장을 찾을 수 있다고 말한다.[34]

적용들

내결함성 다중 처리

정 교수가 인용한 책 임베딩을 연구하기 위한 주요 동기 중 하나는 VLSI 설계의 응용 프로그램을 내결함성 다중 프로세서 조직에 적용하는 것이다.이들 저자가 개발한 DIGENES 시스템에서 멀티프로세서 시스템의 CPU는 책의 척추에 해당하는 논리적인 시퀀스로 배열된다(이 시퀀스가 반드시 이 시스템의 물리적 레이아웃에서 선을 따라 배치되는 것은 아닐 수 있지만).이러한 프로세서를 연결하는 통신 링크는 "번들"로 그룹화되어 책의 페이지에 대응하고 스택처럼 작용한다: 프로세서 중 하나를 새로운 통신 링크의 시작에 연결하면 이전의 모든 링크가 번들의 위로 밀려오며, 다른 프로세서를 통신 링크 끝에 연결하면한 개는 보따리 밑에 있고 다른 것은 모두 아래로 떨어진다.이러한 스택 동작 때문에, 단일 번들은 책 내장에서 단일 페이지의 가장자리를 형성하는 일련의 통신 링크를 처리할 수 있다.이러한 방식으로 링크를 구성함으로써, 네트워크를 구현할 수 있는 충분한 수의 비장애 프로세서가 남아 있는 한, 어떤 프로세서가 결함이 되었는지에 관계없이, 매우 다양한 네트워크 토폴로지를 구현할 수 있다.이 시스템에 의해 구현될 수 있는 네트워크 토폴로지는 정확히 책 두께가 사용 가능한 번들의 수와 동일한 것이다.[39]또한 북 임베딩은 VLSI 구성요소를 회로 층으로 연결하는 와이어의 배치를 모델링하는 데 사용될 수 있다.[49]

스택 정렬

정, 레이튼 & 로젠버그(1987)가 인용한 또 다른 애플리케이션은 스택을 이용한 순열 분류에 관한 것이다.Donald Knuth(1968)의 영향력 있는 결과에 따르면, 수신 요소를 스택에 밀어넣어 데이터 스트림을 처리한 다음 적절하게 선택한 시간에 스택에서 출력 스트림에 이를 푸핑하는 시스템은 초기 순서가 순열 패턴 231을 피하는 순열로 설명될 경우에만 데이터를 정렬할 수 있다.그 이후로 스택과 대기열의 더 일반적인 시스템에 의해 데이터 스트림을 분류하는 유사한 문제에 대한 많은 연구가 있었다.[50]정, 레이튼 & 로젠버그(1987)가 고려한 시스템에서는 입력 데이터 스트림의 각 요소를 여러 스택 중 하나에 밀어 넣어야 한다.그런 다음, 모든 데이터가 이러한 방식으로 밀려나면 해당 스택에서 출력 스트림으로 항목들이 튀어 오른다.Chung 등이 관찰한 바와 같이, 순열에서 파생된 특정 그래프가 척추를 따라 일정한 고정 순서의 정점과 최대 스택 수와 동일한 수의 페이지를 포함하는 책을 포함하는 경우에만 주어진 순열은 이 시스템에 의해 정렬될 수 있다.[39]

교통통제

교통 교차로.관통 차선 4쌍, 회전 포켓 2개, 횡단보도 코너 4개는 책 내장 척추에 14개의 꼭지점 세트로 표현될 수 있으며, 가장자리는 이 지점들 사이의 연결을 나타낸다.

카이넨(1990)이 기술한 바와 같이, 책 임베딩은 통제된 교차로에서 교통 신호의 단계를 설명하는 데 사용될 수 있다.교차로에서 들어오고 나가는 차선(보행자 횡단보도와 자전거 도로의 끝은 물론 자동차 차선도 포함)은 교차로 주변의 시계방향 순서로 책 척추에 내장된 그래프의 정점으로 나타낼 수 있다.들어오는 차선에서 나가는 차선으로 가기 위해 트래픽에 의해 취해지는 교차로를 통과하는 경로는 방향하지 않은 그래프의 가장자리로 나타낼 수 있다.예를 들어, 이 그래프는 연결점에서 U턴이 허용되는 경우에만 해당 구간에서 해당 구간으로의 U턴을 나타내는 동일한 구간 도로의 동일한 구간에 속하는 진입 차선에서 나가는 차선으로 가는 에지를 가질 수 있다.이러한 가장자리의 특정 부분 집합에 대해, 부분 집합은 두 가장자리가 책 임베딩의 단일 페이지에 배치되는 경우 교차하는 가장자리 쌍을 포함하지 않는 경우에만 서로 간섭 없이 모두 통과할 수 있는 경로 집합을 나타낸다.따라서, 이 그래프를 포함하는 책에서는 비 상호 연결 서브셋으로 경로의 파티션을 설명하고, 이 그래프의 책 두께는 (척추에 고정된 포함) 연결점을 통과하는 모든 가능한 트래픽 경로를 포함하는 신호 전달 일정에 필요한 최소 고유 단계 수를 제공한다.[51]

그래프 그리기

골드너-하라리 그래프의 호 다이어그램.평면도를 만들기 위해 파선된 빨간색 선에 의해 그래프의 두 삼각형을 네 개로 세분화하여 그래프 가장자리 중 하나가 선 위와 아래로 모두 확장되도록 하였다.

네트워크 데이터의 시각화에도 북 임베딩이 빈번하게 적용되어 왔다.그래프 도면, 호도[52], 원형 배치의 표준 레이아웃 중 2개는 북 임베딩으로 볼 수 있으며,[53] 클러스터 배치,[44] 동시 임베딩,[54] 3차원 그래프 도면 제작에도 북 임베딩이 적용되었다.[55]

호 다이어그램[52] 또는 선형 내장형[42] 그래프는 선을 따라 그래프의 정점을 배치하고, 그래프의 가장자리를 이 선 위 또는 아래에 반원형으로 그리며, 때로는 선의 세그먼트에 가장자리를 그릴 수도 있다.이 드로잉 스타일은 한 페이지(모든 세미클이 선 위에 있는 경우) 또는 두 페이지(선 양쪽을 모두 사용하는 경우)가 포함된 책에 해당하며, 원래 그래프의 교차 숫자를 연구하는 방법으로 도입되었다.[56][57]2페이지 분량의 책이 임베딩되어 있지 않은 평면 그래프도 비슷한 방식으로 그려질 수 있는데, 선 위와 아래에 여러 개의 반원형으로 가장자리를 나타낼 수 있다.이런 그림은 통상적인 정의에 의해 내재된 책이 아니라 위상적 책 임베딩으로 불려왔다.[58]모든 평면 그래프의 경우, 최대 한 번에 각 가장자리가 척추를 가로지르는 그러한 내장을 항상 찾을 수 있다.[59]

차바탈 그래프의 원형 배치

또 다른 그리기 스타일인 원형 레이아웃에서 그래프의 정점을 원 위에 놓고 가장자리를 원 안이나 바깥으로 그린다.[53]다시 말하지만, 원 내의 가장자리 배치(예: 직선 세그먼트)는 한 페이지짜리 책 도면에 해당하며, 원 내외부의 위치는 두 페이지짜리 책 도면에 해당된다.[60]

양식의 한 페이지 도면에 대해서는 도면의 시각적 잡음을 줄이는 방법으로 교차 횟수를 작게 유지하는 것이 중요하다.교차 횟수를 최소화하는 것은 NP-완전하지만 [42]근사비는 O(log2 n)이며 여기서 n은 정점의 수입니다.[61]1페이지 또는 2페이지의 교차 숫자를 최소화하는 것은 주어진 그래프의 사이클로메틱 번호 또는 교차 번호와 그래프의 트리 너비의 조합으로 매개변수화된 경우 고정 매개변수를 추적할 수 있다.[62][63]교차 복잡성을 줄이기 위한 경험적 접근법도 고안되었는데, 예를 들어, 정점 삽입 순서와 국소 최적화에 기초한다.[53]

가장자리의 고정된 분할이 있는 2페이지 분량의 책은 군집화된 평면성의 한 형태로 해석할 수 있는데, 그래프의 일부(가장자리의 두 부분 집합)가 군집화를 반영하는 방식으로 도면에 배치되는 방식으로 주어진 그래프를 그려야 한다.[44]두 페이지 분량의 책 임베딩은 또한 그래프의 동시 임베딩을 찾는 데 사용되었는데, 두 개의 그래프가 동일한 꼭지점에 주어지고 두 그래프가 모두 직선 가장자리로 평면적으로 그려지는 정점을 찾아야 한다.[54]

2페이지가 넘는 책 임베딩도 그래프의 입체도면을 구성하는 데 활용됐다.특히 우드(2002)는 저용량의 3차원 그리드에 그래프를 내장하는 방법의 하나로 각 페이지 내 꼭지점의 정도를 낮게 유지하는 책 임베딩 공법을 사용했다.[55]

RNA접기

가성비를 보이는 인간 말단소체의 한 조각.책 임베딩의 척추를 따라 파편이 일직선으로 뻗어나간다면, 파란색 염기쌍은 척추 위와 아래를 가로지르지 않는 두 개의 서브셋으로 그려질 수 있어, 이 가성비가 2차 구조를 이루고 있음을 알 수 있다.

RNA 분자가 어떻게 접혀 구조를 형성하는가에 대한 연구에서, 핵산의 2차 구조의 표준 형태는 구조물의 기저귀를 설명하는 선 위의 호 집합과 함께 선을 따라 그려진 염기 연쇄(RNA 염기서열 그 자체)로 도식적으로 설명할 수 있다.즉, 이러한 구조물은 실제로 복잡한 3차원 형태를 가지고 있지만, 이들의 연결성(이차 구조가 존재할 때)은 보다 추상적인 구조, 즉 한 페이지 분량의 책을 내장하여 설명할 수 있다.그러나 모든 RNA 주름이 이런 간단한 방법으로 작용하는 것은 아니다.해슬링거&스태들러(1999)는 2쪽짜리 책 임베딩 형식을 취하는 특정 RNA 가성비에 대해 이른바 '비2차 구조'를 제안했는데, RNA 시퀀스는 다시 선을 따라 그려지지만 베이스펜은 이 선 위와 아래를 모두 호로 그려진다.2차 구조를 형성하기 위해서는 그래프가 최대 3도 이상이어야 한다. 각 베이스는 기본 시퀀스에서 이웃에 대한 두 링크 외에 도표의 하나의 호에만 참여할 수 있다.이 제형의 장점은 우주에 실제로 매듭지어진 구조물을 배제하고, 대부분의 알려진 RNA 유사점들과 일치한다는 사실을 포함한다.[7]

척추 순서는 이 용도에 대해 미리 알려져 있기 때문에 주어진 베이스페어링에 대한 2차 구조의 존재에 대한 테스트는 간단하다.양립 가능한 방법으로 두 페이지에 가장자리를 할당하는 문제는 2-만족도의 한 예로서 또는 가장자리가 기준점이고 가장자리가 기준점 사이의 교차점을 설명하는 원 그래프의 초당성을 시험하는 문제로서 공식화될 수 있다.[7]대신, 보다 효율적으로 해슬링거&스태들러(1999)가 보여주듯이, 입력의 다이어그램 그래프(기본을 순차적으로 사이클로 연결하고 주어진 베이스 포인터를 에지로 추가함으로써 형성된 그래프)가 평면 그래프인 경우에만 2차 구조가 존재한다.[7]이러한 특성화를 통해 2차 구조물을 선형 시간 내에 평면성 시험의 한 예로 인식할 수 있다.

블린 외 (2007) RNA 2차 구조 비교에서 특정 문제의 NP-강도의 입증의 일환으로 2차 구조와 책 임베딩 사이의 연결을 사용했다.[64]그리고 RNA 구조가 2차 구조가 아닌 3차 구조인 경우(즉, 해당 다이어그램에서 2페이지 이상이 필요한 경우), 페이지 번호를 결정하는 것은 다시 NP-hard이다.[65]

계산 복잡성 이론

Pavan, Tewari & Vinodchandran(2012년)은 지시된 그래프에서 도달성 문제에 대한 계산 복잡성 이론을 연구하기 위해 책 임베딩을 사용했다.그들이 관찰했듯이, 두 페이지 방향 그래프의 도달 가능성은 모호하지 않은 로그 공간(로그 공간 복잡성에 대한 아날로그, 모호하지 않은 다항식 시간 문제의 클래스 UP)에서 해결될 수 있다.그러나 3페이지 분량의 지시 그래프의 도달가능성은 비결정론적 로그 공간의 완전한 힘을 필요로 한다.따라서, 책 임베딩은 이 두 가지 복잡성 계층의 구별과 밀접하게 연관되어 있는 것처럼 보인다.[66]

페이지 번호가 일정한[36] 익스팬더 그래프의 존재는 1테이프 비결정론적 튜링 기계에 의한 2테이프 비결정론적 튜링 기계에 대한 2쿼터 시간 시뮬레이션이 없음을 증명하는 핵심 단계다.[67]

수학의 다른 영역

McKenzie & Overbay(2010)는 각 영점 분점 및 0인 각 값 쌍에 대한 가장자리를 만들어 유한 국부 링의 영점 분점으로부터 정의된 그래프를 사용하여 추상 대수에서 책 두께의 적용을 연구한다.[68]

다용지 서열에서, Dynnikov는 매듭과 링크의 위상학적 서적을 연구했는데, 이러한 임베딩은 기호의 조합적 순서에 의해 설명될 수 있고, 두 링크의 위상학적 동등성은 임베딩에 대한 일련의 국지적 변화에 의해 증명될 수 있다는 것을 보여주었다.[69][70]

참조

  1. ^ a b Persinger, C. A. (1966), "Subsets of n-books in E3", Pacific Journal of Mathematics, 18: 169–173, doi:10.2140/pjm.1966.18.169, MR 0195077.
  2. ^ a b Atneosen, Gail Adele (1968), On the embeddability of compacta in n-books: intrinsic and extrinsic properties, Ph.D. thesis, Michigan State University, p. 79, MR 2617705. 또한 참조하십시오.
  3. ^ Kainen, Paul C. (1974), "Some recent results in topological graph theory", in Bari, Ruth A.; Harary, Frank (eds.), Graphs and Combinatorics (Proceedings of the Capital Conference on Graph Theory and Combinatorics at the George Washington University June 18–22, 1973), Lecture Notes in Mathematics, vol. 406, pp. 76–108.
  4. ^ Ollmann, L. Taylor (1973), "On the book thicknesses of various graphs", in Hoffman, Frederick; Levow, Roy B.; Thomas, Robert S. D. (eds.), Proc. 4th Southeastern Conference on Combinatorics, Graph Theory and Computing, Congressus Numerantium, vol. VIII, p. 459.
  5. ^ a b c Yannakakis, Mihalis (1989), "Embedding planar graphs in four pages", Journal of Computer and System Sciences, 38: 36–67, doi:10.1016/0022-0000(89)90032-9
  6. ^ a b c Yannakakis, Mihalis (1986), "Four pages are necessary and sufficient for planar graphs", Proceedings of the 18th ACM Symposium on Theory of Computing (STOC '86), pp. 104–108, doi:10.1145/12130.12141, ISBN 0-89791-193-8, S2CID 5359519.
  7. ^ a b c d e Haslinger, Christian; Stadler, Peter F. (1999), "RNA structures with pseudo-knots: Graph-theoretical, combinatorial, and statistical properties", Bulletin of Mathematical Biology, 61 (3): 437–467, doi:10.1006/bulm.1998.0085, PMC 7197269, PMID 17883226.
  8. ^ Hales, T. C. (1997), "Sphere packings. II", Discrete and Computational Geometry, 18 (2): 135–149, doi:10.1007/PL00009312, MR 1455511.
  9. ^ "스핀"과 "페이지" 용어는 주제에 대한 현대 그래프 이론적 접근방식에서 더 표준적이다."뒤로"와 "리브" 용어는 Persinger(1966년)를 참조한다.
  10. ^ a b c d e f g Bernhart, Frank R.; Kainen, Paul C. (1979), "The book thickness of a graph", Journal of Combinatorial Theory, Series B, 27 (3): 320–331, doi:10.1016/0095-8956(79)90021-2, MR 0554297.
  11. ^ Shahrokhi, Farhad; Székely, László A.; Sýkora, Ondrej; Vrťo, Imrich (1996), "The book crossing number of a graph", Journal of Graph Theory, 21 (4): 413–424, doi:10.1002/(SICI)1097-0118(199604)21:4<413::AID-JGT7>3.3.CO;2-5, MR 1377615.
  12. ^ a b c Heath, Lenwood S. (1987), "Embedding outerplanar graphs in small books", SIAM Journal on Algebraic and Discrete Methods, 8 (2): 198–218, doi:10.1137/0608018, MR 0881181.
  13. ^ Stöhr, Elena (1988), "A trade-off between page number and page width of book embeddings of graphs", Information and Computation, 79 (2): 155–162, doi:10.1016/0890-5401(88)90036-3, MR 0968104.
  14. ^ Stöhr, Elena (1991), "The pagewidth of trivalent planar graphs", Discrete Mathematics, 89 (1): 43–49, doi:10.1016/0012-365X(91)90398-L, MR 1108073.
  15. ^ a b c Enomoto, Hikoe; Miyauchi, Miki Shimabara (1999), "Embedding graphs into a three page book with O(M log N) crossings of edges over the spine", SIAM Journal on Discrete Mathematics, 12 (3): 337–341, doi:10.1137/S0895480195280319, MR 1710241.
  16. ^ a b c Blankenship, Robin; Oporowski, Bogdan (1999), Drawing Subdivisions Of Complete And Complete Bipartite Graphs On Books, Technical Report 1999-4, Department of Mathematics, Louisiana State University, CiteSeerX 10.1.1.36.4358.
  17. ^ Enomoto, Hikoe; Miyauchi, Miki Shimabara; Ota, Katsuhiro (1999), "Lower bounds for the number of edge-crossings over the spine in a topological book embedding of a graph", Discrete Applied Mathematics, 92 (2–3): 149–155, doi:10.1016/S0166-218X(99)00044-X, MR 1697548.
  18. ^ Ábrego, Bernardo M.; Aichholzer, Oswin; Fernández-Merchant, Silvia; Ramos, Pedro; Salazar, Gelasio (2012), "The 2-page crossing number of Kn (extended abstract)", Proceedings of the 28th Annual Symposium on Computational Geometry (SCG'12), ACM, New York, pp. 397–403, doi:10.1145/2261250.2261310, MR 3050657, S2CID 8344088.
  19. ^ 완전한 이분 그래프의 책 두께에 대한 추가적인 결과를 위해,"완전한 이분 그래프의 pagenumber일"면 필기장이 Combinatorial이론, 시리즈 B71(1):111–120, doi:10.1006/jctb.1997.1773, MR1469870, deKlerk가 Mandela, 에티엔;Pasechnik, 드미트리 V, 살라자르, Gelasio(20에노모토, Hikoe, Nakamigawa, Tomoki, 오타, 오토모(1997년)를 참조하십시오.14),"완전한 이분 그래프의 책 도면", 이산화 응용 수학, 167:80–93, arXiv:1210.2918, doi:10.1016/j.dam.2013.11.001, MR3166108, S2CID 40920263.
  20. ^ Sperfeld, Konrad (2013), "On the page number of complete odd-partite graphs", Discrete Mathematics, 313 (17): 1689–1696, doi:10.1016/j.disc.2013.04.028, MR 3061004.
  21. ^ Hasunuma, Toru, 시바타, 유키오(1997년),"책에 드 Bruijn, Kautz과shuffle-exchange 네트워크 묻기", 이산화 응용 수학, 78(1–3):103–116, doi:10.1016(97)00009-7, MR1475820, 다나카, Yuuki, 시바타, 유키오(2010년),"그cube-connected 사이클의 pagenumber일", 수학 컴퓨터 과학으로, 3(1):109–117,. 도이:10.1007/s11786-009-0012-y, MR2596254, S2CID 11830437.또한 참조하 Obrenić, 보자나(1993년),"5페이지에 드 Bruijn과shuffle-exchange 그래프 묻기", SIAM 저널 이산 수학에, 6(4):642–654, doi:10.1137/0406049, MR1241401.
  22. ^ Bekos, Michael A.; Gronemann, Martin; Raftopoulou, Chrysanthi N. (2014), "Two-page book embeddings of 4-planar graphs", Proceedings of the 31st Symposium on Theoretical Aspects of Computer Science, Leibniz International Proceedings in Informatics (LIPIcs), vol. 25, pp. 137–148, arXiv:1401.0684, doi:10.4230/LIPIcs.STACS.2014.137, ISBN 9783939897651.
  23. ^ Heath, Lenny (1984), "Embedding planar graphs In seven pages", Proceedings of the 25th Annual Symposium on Foundations of Computer Science, pp. 74–83, doi:10.1109/SFCS.1984.715903.
  24. ^ a b Bekos, Michael A.; Kaufmann, Micheal; Klute, Fabian; Pupyrev, Sergey; Raftopoulou, Chrysanthi; Ueckerdt, Torsten (2020), "Four Pages Are Indeed Necessary for Planar Graphs", Journal of Computational Geomerty, 1 (11): 332–353, arXiv:2004.07630.
  25. ^ a b c Eppstein, David (2001), Separating geometric thickness from book thickness, arXiv:math.CO/0109195, Bibcode:2001math......9195E.
  26. ^ Dujmović, Vida; Eppstein, David; Hickingbotham, Robert; Morin, Pat; Wood, David R. (August 2021), "Stack-number is not bounded by queue-number", Combinatorica, arXiv:2011.04195, doi:10.1007/s00493-021-4585-7
  27. ^ a b Dujmović, Vida; Wood, David R. (2007), "Graph treewidth and geometric thickness parameters", Discrete and Computational Geometry, 37 (4): 641–670, arXiv:math/0503553, doi:10.1007/s00454-007-1318-7, S2CID 9141367.
  28. ^ Ganley, Joseph L.; Heath, Lenwood S. (2001), "The pagenumber of k-trees is O(k)", Discrete Applied Mathematics, 109 (3): 215–221, doi:10.1016/S0166-218X(00)00178-5, MR 1818238.
  29. ^ Malitz, Seth M. (1994), "Graphs with E edges have pagenumber O(√E)", Journal of Algorithms, 17 (1): 71–84, doi:10.1006/jagm.1994.1027, MR 1279269.
  30. ^ Malitz, Seth M. (1994), "Genus g graphs have pagenumber O(√g)", Journal of Algorithms, 17 (1): 85–109, doi:10.1006/jagm.1994.1028, MR 1279270.
  31. ^ a b c d Nešetřil, Jaroslav; Ossona de Mendez, Patrice (2012), Sparsity: Graphs, Structures, and Algorithms, Algorithms and Combinatorics, vol. 28, Springer, pp. 321–328, doi:10.1007/978-3-642-27875-4, ISBN 978-3-642-27874-7, MR 2920058.
  32. ^ Blankenship, R. (2003), Book Embeddings of Graphs, Ph.D. thesis, Department of Mathematics, Louisiana State University. 네셰틸&오소나 데 멘데스(2012년)가 인용한 바와 같다.
  33. ^ Bekos, Michael A.; Bruckdorfer, Till; Kaufmann, Michael; Raftopoulou, Chrysanthi (2015), "1-Planar graphs have constant book thickness", Algorithms – ESA 2015, Lecture Notes in Computer Science, vol. 9294, Springer, pp. 130–141, doi:10.1007/978-3-662-48350-3_12.
  34. ^ a b Bekos, Michael; Kaufmann, Michael; Zielke, Christian (2015), "The book embedding problem from a SAT-solving perspective", Proc. 23rd International Symposium on Graph Drawing and Network Visualization (GD 2015), pp. 113–125.
  35. ^ Barát, János; Matoušek, Jiří; Wood, David R. (2006), "Bounded-degree graphs have arbitrarily large geometric thickness", Electronic Journal of Combinatorics, 13 (1): R3, doi:10.37236/1029, MR 2200531.
  36. ^ a b Dujmović, Vida, Sidiropoulos, 아나스타시오스, 우드, 데이비드 R.(2015년), 3-Monotone Expanders, arXiv:1501.05020, Bibcode:2015arXiv150105020D, 이는 앞서 결과 부르갱, 장(2009년),"Expanders 및 치수 확장", Comptes Rendus Mathématique, 347(7–8):357–362,에서 끊임없이 pagenumber과 증량제의 존재를 보여 주고 높여 준다. 도이:10.1016/j.crma.2009.02.009, MR2537230, 부르갱, 장, Yehudayoff, 아미르(2013년),"S의 확장 L2(R){\displaystyle \mathrm{SL}_{2}({R})}\mathbb고 단조로운 증량제", 기하학적 및 기능 분석, 23(1):1–41, doi:10.1007/s00039-012-0200-9, MR3037896, S2CID 121554827.참조하라 가릴 자동 소총, Zvi, Kannan, 라비, Szemerédi, Endre(1989년)," 큰 구분 기호로3-pushdown 그래프에", Combinatorica, 9(1):9–19, doi:10.1007/BF02122679, MR1010295, S2CID 37506294, Dvir, Zeev, Wigderson, 애비(2010년),"단조 증량제:생성과 응용 프로그램", 이론 컴퓨팅, 6:291–308, doi:10.4086/toc.2010.v006a012, MR2770077..
  37. ^ Heath, Lenwood S.; Rosenberg, Arnold L. (1992), "Laying out graphs using queues", SIAM Journal on Computing, 21 (5): 927–958, doi:10.1137/0221055, MR 1181408.
  38. ^ Dujmović, Vida; Wood, David R. (2004), "On linear layouts of graphs", Discrete Mathematics & Theoretical Computer Science, 6 (2): 339–357, MR 2081479.
  39. ^ a b c Chung, Fan R. K.; Leighton, Frank Thompson; Rosenberg, Arnold L. (1987), "Embedding graphs in books: A layout problem with applications to VLSI design" (PDF), SIAM Journal on Algebraic and Discrete Methods, 8 (1): 33–58, doi:10.1137/0608002.
  40. ^ Unger, Walter (1992), "The complexity of colouring circle graphs", STACS 92: 9th Annual Symposium on Theoretical Aspects of Computer Science, Cachan, France, February 13–15, 1992, Proceedings, Lecture Notes in Computer Science, vol. 577, Berlin: Springer, pp. 389–400, doi:10.1007/3-540-55210-3_199.
  41. ^ Unger, Walter (1988), "On the k-colouring of circle-graphs", Proceedings of the 5th Symposium on Theoretical Aspects of Computer Science (STACS '88), Lecture Notes in Computer Science, vol. 294, Springer-Verlag, pp. 61–72, doi:10.1007/BFb0035832.
  42. ^ a b c d Masuda, Sumio; Nakajima, Kazuo; Kashiwabara, Toshinobu; Fujisawa, Toshio (1990), "Crossing minimization in linear embeddings of graphs", IEEE Transactions on Computers, 39 (1): 124–127, doi:10.1109/12.46286, MR 1032144.
  43. ^ Garey, M. R.; Johnson, D. S.; Miller, G. L.; Papadimitriou, C. H. (1980), "The complexity of coloring circular arcs and chords", SIAM Journal on Algebraic and Discrete Methods, 1 (2): 216–227, doi:10.1137/0601025, MR 0578325.
  44. ^ a b c Hong, Seok-Hee; Nagamochi, Hiroshi (2009), Two-page book embedding and clustered graph planarity (PDF), Technical report (2009-004 ed.), Dept. of Applied Mathematics and Physics, University of Kyoto, Japan.
  45. ^ Angelini, Patrizio, 디 바르톨로메오, 마르코, 디 바티스타, 주세페(2013년),"칸막이한2-page 책 시험 알고리즘 내장 구현"Graph도면:20일 국제 심포지엄, 승무원 2012년, 레드먼드, WA, 미국, 9월 19–21, 2012년 선택 기술, 강의 노트 컴퓨터 과학으로, 7704 vol., 스프링거,를 대신하여 서명함. 79–89, arXiv:1209.0598, 합치하도록 수정되었다. 도이:10.1007/978-3-642-36763-2_8, MR3067219, S2CID 15360191.
  46. ^ 네셰틸 & 오소나 데 멘데스(2012), 코롤라리 18.1, 페이지 401.
  47. ^ Nešetřil, Jaroslav; Ossona de Mendez, Patrice (2008), "Grad and classes with bounded expansion. II. Algorithmic aspects", European Journal of Combinatorics, 29 (3): 777–791, arXiv:math/0508324, doi:10.1016/j.ejc.2006.07.014, MR 2397336, S2CID 1139740.
  48. ^ 네셰틸 & 오소나 데 멘데스(2012), 정리 18.7, 페이지 405.
  49. ^ Rosenberg, Arnold L. (1986), "Book embeddings and wafer-scale integration", Proceedings of the seventeenth Southeastern international conference on combinatorics, graph theory, and computing (Boca Raton, Fla., 1986), Congressus Numerantium, vol. 54, pp. 217–224, MR 0885282.
  50. ^ Knuth, Donald E. (1968), The Art Of Computer Programming Vol. 1, Boston: Addison-Wesley, Section 2.2.1, Exercises 4 and 5, ISBN 0-201-89683-4, MR 0286317, OCLC 155842391.
  51. ^ Kainen, Paul C. (1990), "The book thickness of a graph. II", Proceedings of the Twentieth Southeastern Conference on Combinatorics, Graph Theory, and Computing (Boca Raton, FL, 1989), Congressus Numerantium, vol. 71, pp. 127–132, MR 1041623.
  52. ^ a b Wattenberg, M. (2002), "Arc diagrams: visualizing structure in strings", Proceedings of IEEE Symposium on Information Visualization (INFOVIS 2002), pp. 110–116, doi:10.1109/INFVIS.2002.1173155, S2CID 881989.
  53. ^ a b c Baur, Michael; Brandes, Ulrik (2005), "Crossing reduction in circular layouts", in van Leeuwen, Jan (ed.), Graph-Theoretic Concepts in Computer Science: 30th International Workshop, WG 2004, Bad Honnef, Germany, June 21-23, 2004, Revised Papers, Lecture Notes in Computer Science, vol. 3353, Springer, pp. 332–343, doi:10.1007/978-3-540-30559-0_28.
  54. ^ a b Angelini, Patrizio; Di Battista, Giuseppe; Frati, Fabrizio; Patrignani, Maurizio; Rutter, Ignaz (2012), "Testing the simultaneous embeddability of two graphs whose intersection is a biconnected or a connected graph", Journal of Discrete Algorithms, 14: 150–172, doi:10.1016/j.jda.2011.12.015, MR 2922068.
  55. ^ a b Wood, David R. (2002), "Bounded degree book embeddings and three-dimensional orthogonal graph drawing", Graph Drawing: 9th International Symposium, GD 2001, Vienna, Austria, September 23–26, 2001, Revised Papers, Lecture Notes in Computer Science, vol. 2265, Springer, Berlin, pp. 312–327, doi:10.1007/3-540-45848-4_25, MR 1962433.
  56. ^ Saaty, Thomas L. (1964), "The minimum number of intersections in complete graphs", Proceedings of the National Academy of Sciences of the United States of America, 52 (3): 688–690, Bibcode:1964PNAS...52..688S, doi:10.1073/pnas.52.3.688, MR 0166772, PMC 300329, PMID 16591215.
  57. ^ Nicholson, T. A. J. (1968), "Permutation procedure for minimising the number of crossings in a network", Proceedings of the Institution of Electrical Engineers, 115: 21–26, doi:10.1049/piee.1968.0004, MR 0311416.
  58. ^ Miyauchi, Miki (2006), "Topological book embedding of bipartite graphs", IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, E89-A (5): 1223–1226, Bibcode:2006IEITF..89.1223M, doi:10.1093/ietfec/e89-a.5.1223.
  59. ^ 조르다노, 프란체스코, 리오타, 주세페;Mchedlidze, 타마라, Symvonis, 안토니오스(2007년),"상승 평면 digraphs의 위로 위상 책 embeddings을 산출하는", 알고리즘과 계산:18일 국제 심포지엄, 아이작 2007년, 센다이, 일본, 12월 17–19, 2007, 회보, 강의 노트 컴퓨터 과학으로,. 172–183, 4835, 스프링거,를 대신하여 서명함 vol.. doi:10.1007/978-3-540-77120-3_17.
  60. ^ He, Hongmei; Sykora, Ondrej (2004), "New circular drawing algorithms", Proceedings of the Workshop on Information Technologies – Applications and Theory (ITAT), Slovakia, September 15–19, 2004.
  61. ^ Shahrokhi, Farhad; Sýkora, Ondrej; Székely, László A.; Vrt'o, Imrich (1995), "Book embeddings and crossing numbers", Graph-Theoretic Concepts in Computer Science: 20th International Workshop, WG '94, Herrsching, Germany, June 16–18, 1994, Proceedings, Lecture Notes in Computer Science, vol. 903, Springer, pp. 256–268, doi:10.1007/3-540-59071-4_53.
  62. ^ 배니 스터, 마이클 J.;Eppstein, 데이비드, 시몬스, 조셉 A(2013년),"almost-trees의 최소화 횡단의 고정형 변수 도야성"Graph도면:21세기 국제 심포지움, 승무원 2013년, 보르도, 프랑스, 9월 23–25, 2013년 선택 기술, 강의 노트 컴퓨터 과학으로, 8242,를 대신하여 서명함. 340–351 vol., arXiv:1308.5741, 합치하도록 수정되었다. doi:10.1007/978-3-319-03841-4_30, S2CID 10142319.
  63. ^ Bannister, Michael J.; Eppstein, David (2014), "Crossing minimization for 1-page and 2-page drawings of graphs with bounded treewidth", Proc. 22nd Int. Symp. Graph Drawing (GD 2014), Lecture Notes in Computer Science, vol. 8871, Springer-Verlag, pp. 210–221, arXiv:1408.6321, doi:10.1007/978-3-662-45803-7_18, MR 3333228.
  64. ^ Blin, 기욤, Fertin, 기욤, Rusu, 아이리나.;Sinoquet, 크리스틴(2007년),"RNA이차 구조 비교의 경도까지.", Combinatorics, 알고리즘, 확률론적 및 실험적 방법:.제1회 국제 심포지엄, ESCAPE 2007년, 항저우, 중국, 4월 7-9,2007, 선택된 논문(PDF), 강의 노트 컴퓨터 과학으로, 4614,를 대신하여 서명함. 140–151, doi:10.1007/978-3-540-74450-4_13 vol. 합치하도록 수정되었다.
  65. ^ Clote, Peter; Dobrev, Stefan; Dotu, Ivan; Kranakis, Evangelos; Krizanc, Danny; Urrutia, Jorge (2012), "On the page number of RNA secondary structures with pseudoknots", Journal of Mathematical Biology, 65 (6–7): 1337–1357, doi:10.1007/s00285-011-0493-6, PMID 22159642, S2CID 8700502.
  66. ^ Pavan, A.; Tewari, Raghunath; Vinodchandran, N. V. (2012), "On the power of unambiguity in log-space", Computational Complexity, 21 (4): 643–670, arXiv:1001.2034, doi:10.1007/s00037-012-0047-3, MR 2988774, S2CID 8666071.
  67. ^ Galil, Zvi; Kannan, Ravi; Szemerédi, Endre (1989), "On nontrivial separators for k-page graphs and simulations by nondeterministic one-tape Turing machines", Journal of Computer and System Sciences, 38 (1): 134–149, doi:10.1016/0022-0000(89)90036-6.
  68. ^ McKenzie, Thomas; Overbay, Shannon (2010), "Book embeddings and zero divisors", Ars Combinatoria, 95: 55–63, MR 2656248.
  69. ^ Dynnikov, I. A. (1999), "Three-page approach to knot theory. Coding and local motions", Rossiĭskaya Akademiya Nauk, 33 (4): 25–37, 96, doi:10.1007/BF02467109, MR 1746427, S2CID 121089736.
  70. ^ Dynnikov, I. A. (2001), "A new way to represent links, one-dimensional formalism and untangling technology", Acta Applicandae Mathematicae, 69 (3): 243–283, doi:10.1023/A:1014299416618, MR 1885279, S2CID 116488382.