Osadzanie książki

Trzystronicowa książka zawierająca pełny wykres

K 5

. Ponieważ nie jest to graf planarny , nie można osadzić tego wykresu bez przecięć na mniejszej liczbie stron, więc jego grubość książki wynosi trzy.

W teorii grafów osadzenie książki jest uogólnieniem płaskiego osadzania wykresu na osadzenie w książce , zbiorze półpłaszczyzn, z których wszystkie mają tę samą linię co ich granica. Zwykle wierzchołki grafu muszą leżeć na tej linii granicznej, zwanej kręgosłupem , a krawędzie muszą pozostawać w obrębie jednej półpłaszczyzny. Grubość książki wykresu to najmniejsza możliwa liczba półpłaszczyzn dla dowolnego osadzenia książki w grafie. Grubość książki jest również nazywana numerem strony , numerem stosu lub stałą grubością zewnętrzną . Osadzenia książek zostały również wykorzystane do zdefiniowania kilku innych niezmienników wykresów , w tym szerokości strony i numeru przecięcia książki.

Każdy wykres z n $wierzchołkami$ $wzór$ co najwyżej grubość książki podaje dokładną grubość książki dla całych Grafy o grubości książki 1 są grafami płaszczyzny zewnętrznej . Grafy o grubości książki co najwyżej dwa są grafami subhamiltonowskimi , które są zawsze planarne ; bardziej ogólnie, każdy graf planarny ma grubość książki co najwyżej cztery. Wszystkie rodziny grafów z mniejszymi domknięciami , aw szczególności grafy z ograniczoną szerokością drzewa lub ograniczonym rodzajem , również mają ograniczoną grubość księgi. Określenie dokładnej grubości książki danego wykresu jest NP-trudne , ze znajomością ustalonego wierzchołka uporządkowanego wzdłuż grzbietu książki lub bez. Testowanie istnienia trzystronicowej książki osadzonej w grafie, biorąc pod uwagę ustaloną kolejność wierzchołków wzdłuż grzbietu osadzenia, ma nieznaną złożoność obliczeniową: nie wiadomo, czy można go rozwiązać w czasie wielomianowym, ani nie jest NP-trudny .

Jedna z pierwotnych motywacji do badania osadzania książek dotyczyła zastosowań w projektowaniu VLSI , w których wierzchołki osadzania książki reprezentują elementy obwodu, a przewody reprezentują połączenia między nimi. Osadzanie książek ma również zastosowanie w rysowaniu wykresów , gdzie dwa standardowe style wizualizacji wykresów, diagramów łukowych i układów kołowych można konstruować za pomocą osadzania książek.

W planowaniu transportu różne źródła i miejsca docelowe ruchu pieszego i samochodowego, które spotykają się i oddziałują na sygnalizację świetlną, można modelować matematycznie jako wierzchołki grafu, z krawędziami łączącymi różne pary źródło-miejsce docelowe. Osadzenie tego wykresu w książce można wykorzystać do zaprojektowania harmonogramu, który umożliwia ruch całego ruchu przez skrzyżowanie przy jak najmniejszej liczbie faz sygnalizacji. W bioinformatycznych obejmujących pofałdowaną strukturę RNA , jednostronicowe osadzenie książki reprezentuje klasyczne formy drugorzędowej struktury kwasu nukleinowego , a osadzenie dwustronicowej książki reprezentuje pseudowęzły . Inne zastosowania osadzania książek obejmują algebrę abstrakcyjną i teorię węzłów .

Historia

Pojęcie książki jako przestrzeni topologicznej zostało zdefiniowane przez CA Persingera i Gail Atneosen w latach 60. XX wieku. W ramach tej pracy Atneosen rozważał już osadzenie wykresów w książkach. Badane przez niego osadzenie wykorzystywało tę samą definicję, co osadzenie grafów w dowolnej innej przestrzeni topologicznej: wierzchołki są reprezentowane przez różne punkty, krawędzie są reprezentowane przez krzywe, a jedynym sposobem, w jaki dwie krawędzie mogą się przecinać, jest ich spotkanie we wspólnym punkcie końcowym.

We wczesnych latach siedemdziesiątych Paul C. Kainen i L. Taylor Ollmann opracowali bardziej ograniczony typ osadzania, który zaczęto stosować w większości późniejszych badań. W ich sformułowaniu wierzchołki wykresu muszą znajdować się wzdłuż grzbietu książki, a każda krawędź musi leżeć na jednej stronie. Do ważnych kamieni milowych w późniejszym rozwoju osadzania książek należy dowód Mihalisa Yannakakisa pod koniec lat 80. XX wieku, że grafy planarne mają grubość książki co najwyżej cztery, oraz odkrycie pod koniec lat 90. bliskich powiązań między osadzaniem książek a bioinformatyką .

Definicje

Wykres użyteczności K _3,3 nie ma osadzenia w 2-stronicowej książce, ale można go narysować tak, jak pokazano w 2-stronicowej książce z tylko jednym skrzyżowaniem. Dlatego jego 2-stronicowy numer skrzyżowania to 1.

To 1-stronicowe osadzenie wykresu rombu ma szerokość strony 3, ponieważ żółty promień przecina trzy krawędzie.

Książka to szczególny rodzaj przestrzeni topologicznej , zwany też wachlarzem półpłaszczyzn . Składa się z pojedynczej linii $ℓ$ , zwanej grzbietem lub tyłem książki, wraz ze zbiorem jednej lub więcej półpłaszczyzn , zwanych stronami lub kartami książki, z których każda ma grzbiet jako granicę. Książki o skończonej liczbie stron można osadzić w przestrzeni trójwymiarowej, na przykład wybierając $ℓ$ jako oś $z$ kartezjańskiego układu współrzędnych i wybierając strony jako $k$ półpłaszczyzn, których kąt dwuścienny względem $xz$ -plane jest całkowitą wielokrotnością $2 π / k$ .

Rysowanie książkowe skończonego grafu $G$ na księdze $B$ jest rysowaniem G na $B$ w taki sposób, że każdy wierzchołek $G$ jest narysowany jako punkt na grzbiecie $B$ , a każda krawędź $G jest$ $narysowana$ jako krzywa leżąca w pojedyncza strona $B.$ K $-$ stronicowy numer skrzyżowania książki G to minimalna liczba przecięć w $k$ -stronicowym rysunku książki $.$

Książkowe osadzenie G w $B$ to rysunek książkowy, który $tworzy$ $wykres$ osadzania G w $B$ . Oznacza to, że jest to rysunek książkowy $G$ na $B$ , który nie ma żadnych skrzyżowań krawędzi. Każdy graf skończony ma książkę osadzoną w książce o wystarczająco dużej liczbie stron. Na przykład zawsze można osadzić każdą krawędź wykresu na osobnej stronie. Grubość książki , numer strony lub liczba stosu G $to$ minimalna liczba stron wymagana do osadzenia książki $G$ . Innym parametrem, który mierzy jakość osadzenia książki, poza liczbą stron, jest jej szerokość strony . Jest to maksymalna liczba krawędzi, które może przekroczyć promień prostopadły do grzbietu w obrębie jednej strony. Równoważnie (w przypadku osadzania książek, w których każda krawędź jest rysowana jako monotoniczna krzywa), jest to maksymalny rozmiar podzbioru krawędzi na jednej stronie, taki że odstępy określone na grzbiecie przez pary punktów końcowych wszystkich krawędzi przecinają się .

Dla tych definicji kluczowe jest, aby krawędzie mogły pozostać tylko na jednej stronie książki. Jak już zauważył Atneosen, jeśli zamiast tego krawędzie mogą przechodzić z jednej strony na drugą wzdłuż grzbietu książki, to każdy wykres może być osadzony w trzystronicowej książce. W przypadku takiego osadzenia trzystronicowej książki topologicznej , w której dozwolone są przecięcia grzbietów, każdy wykres może być osadzony z co najwyżej logarytmiczną liczbą przecięć grzbietów na krawędź, a niektóre grafy wymagają takiej liczby przecięć grzbietów.

Konkretne wykresy

Jak pokazano na pierwszym rysunku, grubość książki kompletnego grafu $K 5$ wynosi trzy: jako graf nieplanarny grubość książki jest większa niż dwa, ale istnieje książka osadzona z trzema stronami. Mówiąc bardziej ogólnie, grubość księgi każdego pełnego wykresu z $n \geq 4$ wierzchołkami wynosi dokładnie ${\ Displaystyle \ lceil n/2 \ rceil}$ . Ten wynik daje również górną granicę maksymalnej możliwej grubości książki dowolnego wykresu $n$ -wierzchołków.

Dwustronicowy numer przecięcia pełnego wykresu $K n$ to

{\ Displaystyle {\ Frac {1} {4}} {\ biggl \ lfloor} {\ Frac {n} {2}}{\biggr \rfloor }{\biggl \lfloor }{\frac {n-1}{2}}{\biggr \rfloor }{\biggl \lfloor }{\frac {n-2}{2 }}{\biggr \rfloor }{\biggl \lfloor }{\frac {n-3}{2}}{\biggr \rfloor },}

pasujące do wciąż niesprawdzonej hipotezy Anthony'ego Hilla na temat tego, jaka powinna być nieograniczona liczba przejść na tym wykresie. Oznacza to, że jeśli hipoteza Hilla jest poprawna, to rysunek tego wykresu, który minimalizuje liczbę skrzyżowań, jest rysunkiem dwustronicowym.

Grubość księgi kompletnego grafu dwudzielnego $Ka (, b$ wynosi co najwyżej $min a, b)$ . Aby skonstruować rysunek o tej grubości książki, dla każdego wierzchołka na mniejszej stronie bipartycji można umieścić krawędzie incydentne z tym wierzchołkiem na własnej stronie. To ograniczenie nie zawsze jest ścisłe; na przykład $K 4,4$ ma grubość książki trzy, a nie cztery. Jednakże, gdy dwie strony wykresu są bardzo niezrównoważone, przy czym $b > a (a - 1)$ , grubość księgi $K a, b$ wynosi dokładnie $a$ .

Dla grafu Turána $T (kr, r)$ ( pełny wieloczęściowy graf $K k, k,...$ utworzony z $r$ niezależnych zbiorów k wierzchołków na niezależny zbiór, z krawędzią pomiędzy każdymi dwoma wierzchołkami z $różnych$ niezależnych zbiorów) grubość książki $t$ jest wciśnięte pomiędzy

{\ Displaystyle \ lewo \ lceil {\ Frac {k (r-1)}} {2}} \ prawo \ rceil \ równoważnik t \ równoważnik \ lewo \lceil {\frac {kr}{2}}\right\rceil}

a gdy $r$ jest nieparzyste, górną granicę można poprawić

{\ Displaystyle t \ równoważnik (r-1) \ lewo \ lceil {\ Frac {k} {2}} \ prawo \ rceil + \ lewo \ lceil {\ Frac {k} {4}} \ prawo \ rceil.}

Grubość księgi binarnych grafów de Bruijna , grafów losowo-wymiennych i cykli połączonych sześciennie (gdy te grafy są wystarczająco duże, aby były niepłaskie) wynosi dokładnie trzy.

Nieruchomości

Planarność i planarność zewnętrzna

Goldnera – Harary'ego , wykres planarny o grubości książki trzy

Grubość książki danego grafu $G$ wynosi co najwyżej jeden wtedy i tylko wtedy, gdy $G$ jest grafem planarnym . Graf planarny to graf z planarnym osadzeniem, w którym wszystkie wierzchołki należą do zewnętrznej powierzchni osadzania. W przypadku takiego wykresu umieszczenie wierzchołków w tej samej kolejności wzdłuż grzbietu, w jakiej pojawiają się na zewnętrznej powierzchni, zapewnia jednostronicowe osadzenie danego grafu w książce. ( Punkt artykulacji wykresu z konieczności pojawi się więcej niż jeden raz w cyklicznym porządku wierzchołków wokół zewnętrznej ściany, ale tylko jedna z tych kopii powinna zostać uwzględniona w osadzeniu książki). I odwrotnie, osadzanie jednej strony w książce jest automatycznie osadzanie w płaszczyźnie zewnętrznej. Bo jeśli wykres jest osadzony na jednej stronie, a do grzbietu jest dołączona kolejna półpłaszczyzna, aby rozszerzyć jej stronę do całej płaszczyzny, to zewnętrzna powierzchnia osadzania obejmuje całą dodaną półpłaszczyznę, a wszystkie wierzchołki leżą na tej zewnętrznej stronie.

Każde osadzenie dwustronicowej książki jest szczególnym przypadkiem osadzania planarnego, ponieważ połączenie dwóch stron książki jest przestrzenią topologicznie równoważną całej płaszczyźnie. Dlatego każdy graf o grubości książki dwa jest automatycznie grafem planarnym . Dokładniej, grubość książki grafu $G$ wynosi co najwyżej dwa wtedy i tylko wtedy, gdy $G$ jest podgrafem grafu planarnego, który ma cykl Hamiltona . Jeśli graf zostanie osadzony na dwóch stronach, można go rozszerzyć do płaskiego wykresu Hamiltona, dodając (na dowolnej stronie) dodatkowe krawędzie między dowolnymi dwoma kolejnymi wierzchołkami wzdłuż kręgosłupa, które jeszcze nie sąsiadują, oraz między pierwszym a ostatnim kręgosłupem wierzchołki. Goldnera -Harary'ego stanowi przykład wykresu planarnego, który nie ma grubości książki dwa: jest to maksymalny wykres planarny , więc nie jest możliwe dodanie do niego żadnych krawędzi przy zachowaniu planarności i nie ma Cykl Hamiltona . Ze względu na charakteryzację cyklami hamiltonowskimi grafy, które mają osadzenie dwustronicowej książki, są również znane jako grafy subhamiltonowskie .

Wszystkie grafy planarne, których maksymalny stopień wynosi co najwyżej cztery, mają grubość książki co najwyżej dwa. Planarne 3-drzewa mają grubość książki co najwyżej trzy. Mówiąc bardziej ogólnie, wszystkie grafy planarne mają grubość książki cztery. Mihalis Yannakakis stwierdził w 1986 roku, że istnieją pewne grafy planarne, które mają grubość książki dokładnie cztery. Jednak szczegółowy dowód tego twierdzenia, ogłoszony w kolejnym artykule w czasopiśmie, był znany dopiero w 2020 roku, kiedy Bekos i in. przedstawił grafy planarne o szerokości drzewa 4, które wymagają czterech stron w dowolnym osadzeniu książki.

Zachowanie w podpodziałach

Grubość książki wykresu rombowego wzrasta po podziale krawędzi

Podział każdej krawędzi grafu na ścieżki dwukrawędziowe, poprzez dodanie nowych wierzchołków w obrębie każdej krawędzi, może czasami zwiększyć grubość książki. Na przykład graf diamentowy ma grubość księgi jeden (jest płaszczyzną zewnętrzną), ale jego podział ma grubość księgi drugą (jest planarny i subhamiltonowski, ale nie na płaszczyźnie zewnętrznej). Jednak ten proces podziału może czasami znacznie zmniejszyć grubość księgi podzielonego wykresu. Na przykład grubość książki całego wykresu $K n$ jest proporcjonalna do jego liczby wierzchołków, ale podzielenie każdej z jego krawędzi na ścieżkę dwukrawędziową daje podział, którego grubość książki jest znacznie mniejsza, tylko ${\ Displaystyle O({\sqrt {n}})}$ . Pomimo istnienia przykładów takich jak ten, Blankenship i Oporowski (1999) przypuszczali , że grubość księgi podpodziału nie może być dużo mniejsza niż grubość oryginalnego wykresu. W szczególności przypuszczali, że istnieje funkcja $f$ taka, że dla każdego wykresu $G$ i dla wykresu $H$ utworzonego przez zastąpienie każdej krawędzi w $G$ ścieżką dwukrawędziową, jeśli grubość książki $H$ wynosi $t$ , to grubość księgi $G$ wynosi co najwyżej $f (t)$ . Ich przypuszczenia okazały się fałszywe: grafy utworzone przez iloczyny kartezjańskie gwiazd i trójkątnych nachyleń mają nieograniczoną grubość książki, ale podzielenie ich krawędzi na sześciokrawędziowe ścieżki zmniejsza ich grubość książki do trzech.

Związek z innymi niezmiennikami grafu

Grubość książki jest związana z grubością , liczbą grafów planarnych potrzebnych do pokrycia krawędzi danego grafu. Graf $G$ ma grubość $θ,$ jeśli można go narysować na płaszczyźnie, a jego krawędzie pokolorować kolorami $θ$ w taki sposób, aby krawędzie tego samego koloru nie przecinały się. Analogicznie graf $G$ ma grubość książki $θ$ , jeśli można go narysować na półpłaszczyźnie , z wierzchołkami na granicy półpłaszczyzny, z krawędziami pokolorowanymi kolorami $θ$ bez przecinania się dwóch krawędzi tego samego koloru. W tym sformułowaniu grubości książki kolory krawędzi odpowiadają stronom oprawy książki. Jednak grubość i grubość książki mogą się bardzo różnić od siebie: istnieją wykresy ( podziały kompletnych wykresów ), które mają nieograniczoną grubość książki, pomimo grubości drugiej.

Grafy o szerokości drzewa $k$ mają grubość książki co najwyżej $k + 1$ i to ograniczenie jest ścisłe dla $k > 2$ . Wykresy z $m$ krawędziami mają grubość książki , a wykresy rodzaju $g$ mają grubość książki $} )}$ $)$ . Mówiąc bardziej ogólnie, każda rodzina grafów z mniejszymi domknięciami ma ograniczoną grubość książki. Z drugiej strony grafy 1-płaszczyznowe , które nie są domknięte pod drugorzędnymi, również mają ograniczoną grubość książki, ale niektóre grafy 1-płaszczyznowe, w tym $K 2,2,2,2$ , mają grubość księgi co najmniej cztery.

Każdy płytki minor grafu o ograniczonej grubości książki jest grafem rzadkim , którego stosunek krawędzi do wierzchołków jest ograniczony stałą zależną tylko od głębokości minora i grubości książki. Oznacza to, że w terminologii Nešetřila i Ossony de Mendez (2012) wykresy ograniczonej grubości książki mają ograniczoną ekspansję . Jednak nawet wykresy o ograniczonym stopniu , co jest znacznie silniejszym wymaganiem niż ograniczona ekspansja, mogą mieć nieograniczoną grubość książki.

Ponieważ wykresy o grubości książki dwa są grafami planarnymi, są zgodne z twierdzeniem o separatorze planarnym : mają separatory, podzbiory wierzchołków, których usunięcie dzieli wykres na części, z których każdy ma co najwyżej $2 n / 3$ wierzchołki, z tylko ${\ Displaystyle O({\sqrt {n}})}$ wierzchołków w separatorze. Tutaj $n$ odnosi się do liczby wierzchołków w grafie. Istnieją jednak grafy o grubości książki trzy, które nie mają separatorów o rozmiarze podliniowym.

Krawędzie w obrębie pojedynczej strony osadzonej książki zachowują się w pewien sposób jak struktura danych stosu . Można to sformalizować, rozważając dowolną sekwencję operacji push i pop na stosie i tworząc graf, w którym operacje stosu odpowiadają wierzchołkom grafu, umieszczonym w kolejności wzdłuż grzbietu osadzonej książki. Następnie, jeśli narysujemy krawędź z każdej operacji pop, która usuwa obiekt $x$ ze stosu, do poprzedniej operacji push, która wypchnęła $x$ , wynikowy wykres będzie automatycznie osadzony na jednej stronie. Z tego powodu numer strony wykresu został również nazwany jego numerem stosu . W ten sam sposób można rozważyć dowolną sekwencję operacji enqueue i dequeue struktury danych kolejki i utworzyć graf, którego wierzchołkami są te operacje, ułożone w kolejności na grzbiecie pojedynczej strony, z krawędzią między nimi operacja enqueue i odpowiadające jej usuwanie z kolejki. Następnie na tym wykresie każde dwie krawędzie przecinają się lub pokrywają rozłączne interwały na grzbiecie. Przez analogię badacze zdefiniowali osadzenie w kolejce grafu jako osadzenie w księdze topologicznej w taki sposób, że każdy wierzchołek leży na grzbiecie, każda krawędź leży na jednej stronie, a każde dwie krawędzie na tej samej stronie albo krzyżują się, albo pokrywają rozłącznie odstępy na kręgosłupie. Minimalna liczba stron potrzebnych do osadzenia grafu w kolejce nazywana jest jego numerem kolejki .

Złożoność obliczeniowa

Wykres kołowy , wykres przecięcia cięciw koła. W przypadku osadzania książek ze stałą kolejnością wierzchołków znalezienie grubości książki jest równoznaczne z kolorowaniem pochodnego wykresu kołowego.

Znalezienie grubości książki wykresu jest NP-trudne . Wynika to z faktu, że znajdowanie cykli Hamiltona w maksymalnych grafach planarnych jest NP-zupełne . W maksymalnym grafie planarnym grubość księgi wynosi dwa wtedy i tylko wtedy, gdy istnieje cykl Hamiltona. Dlatego testowanie, czy grubość księgi danego maksymalnego wykresu planarnego wynosi dwa, jest również NP-zupełne.

Jeśli uporządkowanie wierzchołków grafu wzdłuż grzbietu osadzania jest ustalone, to dwustronicowe osadzanie (jeśli istnieje) można znaleźć w czasie liniowym, jako przykład testowania planarności dla grafu utworzonego przez zwiększenie danych graf z cyklem łączącym wierzchołki w kolejności ich grzbietów. Unger (1992) twierdził, że znalezienie osadzania trzech stron ze stałą kolejnością grzbietów można również przeprowadzić w czasie wielomianowym , chociaż jego opis tego wyniku pomija wiele szczegółów. Jednak w przypadku wykresów, które wymagają czterech lub więcej stron, problem znalezienia osadzania z minimalną możliwą liczbą stron pozostaje NP-trudny, poprzez równoważność NP-trudnego problemu kolorowania wykresów kołowych , wykresów przecięcia akordów a okrąg . Biorąc pod uwagę graf $G$ ze stałym uporządkowaniem wierzchołków, narysowanie tych wierzchołków w tej samej kolejności wokół okręgu i narysowanie krawędzi $G$ jako odcinków linii tworzy zbiór akordów reprezentujących $G$ . Można wtedy utworzyć wykres kołowy, który ma akordy tego diagramu jako wierzchołki i przecinające się pary akordów jako krawędzie. Kolorowanie wykresu kołowego przedstawia podział krawędzi $G$ na podzbiory, które można narysować bez przecinania na jednej stronie. Dlatego optymalna kolorystyka jest równoważna z optymalnym osadzeniem książki. Ponieważ kolorowanie wykresu kołowego czterema lub więcej kolorami jest NP-trudne i ponieważ każdy wykres kołowy można utworzyć w ten sposób z jakiegoś problemu z osadzeniem książki, wynika z tego, że optymalne osadzanie książki jest również NP-trudne. W przypadku stałego uporządkowania wierzchołków na grzbiecie dwustronicowego rysunku książkowego zminimalizowanie liczby przecięć jest również NP-trudne, gdy liczba ta jest różna od zera.

Jeśli kolejność grzbietów jest nieznana, ale podany jest podział krawędzi na dwie strony, to możliwe jest znalezienie 2-stronicowego osadzania (jeśli istnieje) w czasie liniowym za pomocą algorytmu opartego na drzewach SPQR . Jednak znalezienie 2-stronicowego osadzania jest NP-zupełne, gdy nie jest znana ani kolejność grzbietu, ani partycja krawędzi. Znalezienie numeru przecięcia książki wykresu jest również NP-trudne, ze względu na NP-zupełność specjalnego przypadku testowania, czy liczba przecięć 2-stronicowych wynosi zero.

W wyniku ograniczonej ekspansji, problem izomorfizmu podgrafu polegający na znalezieniu, czy wykres wzorca o ograniczonym rozmiarze istnieje jako podgraf większego grafu, można rozwiązać w czasie liniowym, gdy większy wykres ma ograniczoną grubość książki. To samo dotyczy wykrywania, czy graf wzorcowy jest indukowanym podgrafem większego grafu, czy też ma homomorfizm grafu z większym grafem. Z tego samego powodu problem sprawdzenia, czy wykres o ograniczonej grubości książki jest zgodny z daną formułą logiki pierwszego rzędu, jest wykonalny z ustalonymi parametrami .

Bekos, Kaufmann i Zielke (2015) opisują system znajdowania optymalnych osadzeń książek poprzez przekształcenie problemu w wystąpienie problemu spełnialności Boole'a i zastosowanie rozwiązania SAT do powstałego problemu. Twierdzą, że ich system jest w stanie znaleźć optymalne osadzenie dla maksymalnych grafów planarnych o 400 wierzchołkach w ciągu około 20 minut.

Aplikacje

Odporne na błędy przetwarzanie wieloprocesowe

Jedna z głównych motywacji do studiowania osadzania książek, cytowana przez Chunga, Leightona i Rosenberga (1987) , dotyczy zastosowania w projektowaniu VLSI do organizacji wieloprocesorów odpornych na uszkodzenia . W opracowanym przez tych autorów systemie DIOGENES procesory systemu wieloprocesorowego są ułożone w logiczną sekwencję odpowiadającą grzbietowi książki (chociaż sekwencja ta niekoniecznie musi być umieszczona wzdłuż linii w fizycznym układzie tego systemu). Łącza komunikacyjne łączące te procesory są pogrupowane w „wiązki”, które odpowiadają stronom książki i działają jak stosy : podłączenie jednego z procesorów do początku nowego łącza komunikacyjnego przesuwa wszystkie poprzednie łącza w górę w wiązce, a połączenie innego procesora do końca łącza komunikacyjnego łączy go z tym na dole pakietu i odrzuca wszystkie pozostałe. Ze względu na takie zachowanie stosu pojedynczy pakiet może obsłużyć zestaw łączy komunikacyjnych, które tworzą krawędzie pojedynczej strony w osadzeniu książki. Organizując łącza w ten sposób, można zaimplementować szeroką gamę różnych topologii sieci, niezależnie od tego, które procesory uległy awarii, o ile pozostaje wystarczająca liczba nieuszkodzonych procesorów do wdrożenia sieci. Topologie sieci, które mogą być zaimplementowane przez ten system, to dokładnie te topologie, których grubość książki jest co najwyżej równa liczbie udostępnionych wiązek. Osadzanie książek może być również wykorzystywane do modelowania rozmieszczenia przewodów łączących komponenty VLSI w warstwach obwodu.

Sortowanie stosu

Inne zastosowanie cytowane przez Chunga, Leightona i Rosenberga (1987) dotyczy sortowania permutacji za pomocą stosów . Wpływowe wyniki Donalda Knutha ( 1968 ) pokazały, że system, który przetwarza strumień danych poprzez umieszczanie przychodzących elementów na stosie, a następnie, w odpowiednio dobranych momentach, umieszczanie ich ze stosu na strumieniu wyjściowym, może sortować dane wtedy i tylko wtedy, gdy jego początkowa kolejność jest opisana przez permutację , która unika wzorca permutacji 231. Od tego czasu wykonano wiele pracy nad podobnymi problemami sortowania strumieni danych według bardziej ogólnych systemów stosów i kolejek. W systemie rozważanym przez Chunga, Leightona i Rosenberga (1987) każdy element ze strumienia danych wejściowych musi zostać zepchnięty na jeden z kilku stosów. Następnie, gdy wszystkie dane zostaną wypchnięte w ten sposób, elementy są zdejmowane z tych stosów (w odpowiedniej kolejności) do strumienia wyjściowego. Jak Chung i in. zauważ, że dana permutacja może być posortowana według tego systemu wtedy i tylko wtedy, gdy pewien graf wyprowadzony z permutacji ma księgę osadzoną z wierzchołkami w pewnym ustalonym porządku wzdłuż grzbietu i z liczbą stron, która jest co najwyżej równa do ilości stosów.

Kontrola ruchu

Skrzyżowanie ruchu. Cztery wchodzące i cztery wychodzące pary pasów przelotowych, dwie kieszenie zakrętów i cztery rogi przejścia dla pieszych można przedstawić jako zestaw 14 wierzchołków na grzbiecie osadzonej książki, z krawędziami reprezentującymi połączenia między tymi punktami.

Jak opisał Kainen (1990) , do opisu faz sygnalizacji świetlnej na kontrolowanym skrzyżowaniu można zastosować osadzenie książki. Na skrzyżowaniu pasy ruchu wchodzące i wychodzące (w tym końce przejść dla pieszych i ścieżek rowerowych oraz pasy dla pojazdów mechanicznych) można przedstawić jako wierzchołki grafu umieszczone na grzbiecie książki osadzone w ich kierunku zgodnym z ruchem wskazówek zegara porządek wokół skrzyżowania. Ścieżki przez skrzyżowanie, pokonywane przez ruch drogowy, aby dostać się z pasa wjeżdżającego na pas wychodzący, można przedstawić jako krawędzie wykresu nieskierowanego. Na przykład ten wykres może mieć krawędź między wjeżdżającym a wyjeżdżającym pasem ruchu, które należą do tego samego segmentu drogi, reprezentującą zawracanie z tego segmentu z powrotem do tego segmentu, tylko jeśli zawracanie jest dozwolone na węzeł. Dla danego podzbioru tych krawędzi, podzbiór ten reprezentuje zbiór ścieżek, które wszystkie mogą być pokonywane bez wzajemnej interferencji wtedy i tylko wtedy, gdy podzbiór nie zawiera żadnej pary krawędzi, które przecinałyby się, gdyby dwie krawędzie były umieszczone w jednym strona osadzenia książki. Zatem osadzenie książki tego wykresu opisuje podział ścieżek na niezakłócające podzbiory, a grubość książki tego wykresu (z jego stałym osadzeniem na grzbiecie) daje minimalną liczbę odrębnych faz potrzebnych do harmonogramu sygnalizacji, który obejmuje wszystkie możliwe ciągi komunikacyjne przez skrzyżowanie.

Rysunek wykresu

Diagram łukowy wykresu Goldnera-Harary'ego . W celu utworzenia diagramu planarnego dwa trójkąty wykresu zostały podzielone na cztery przez przerywaną czerwoną linię, powodując, że jedna z krawędzi wykresu rozciąga się zarówno powyżej, jak i poniżej linii.

Osadzanie książek było również często stosowane w wizualizacji danych sieciowych. Dwa standardowe układy w rysowaniu wykresów , diagramy łukowe i układy kołowe, można postrzegać jako osadzenia w książkach, a osadzanie w książkach zostało również zastosowane w konstrukcji układów klastrowych, równoczesnych osadzaniach i trójwymiarowych rysunkach wykresów.

Diagram łukowy lub osadzanie liniowe umieszcza wierzchołki wykresu wzdłuż linii i rysuje krawędzie wykresu jako półkola powyżej lub poniżej tej linii, czasami umożliwiając również rysowanie krawędzi na odcinkach linii. Ten styl rysowania odpowiada osadzeniu książki z jedną stroną (jeśli wszystkie półkola znajdują się nad linią) lub dwiema stronami (jeśli używane są obie strony linii) i został pierwotnie wprowadzony jako sposób badania przecinających się liczb wykresów . Wykresy planarne, które nie mają osadzonych dwustronicowych książek, można również rysować w podobny sposób, umożliwiając reprezentację ich krawędzi przez wiele półokręgów powyżej i poniżej linii. Taki rysunek nie jest osadzeniem książki według zwykłej definicji, ale został nazwany topologicznym osadzeniem książki . Dla każdego grafu planarnego zawsze można znaleźć takie osadzenie, w którym każda krawędź przecina grzbiet co najwyżej raz.

Okrągły układ wykresu Chvátal

W innym stylu rysowania, układzie kołowym , wierzchołki wykresu są umieszczane na okręgu, a krawędzie są rysowane wewnątrz lub na zewnątrz okręgu. Ponownie, umieszczenie krawędzi w okręgu (na przykład jako odcinki linii prostych) odpowiada jednostronicowemu rysunkowi książkowemu, podczas gdy umieszczenie zarówno wewnątrz, jak i na zewnątrz okręgu odpowiada dwustronicowemu rysunkowi książkowemu.

W przypadku jednostronicowych rysunków obu stylów ważne jest, aby liczba przecięć była niewielka, aby zmniejszyć wizualny bałagan na rysunku. Minimalizowanie liczby skrzyżowań jest NP-zupełne , ale można je przybliżyć współczynnikiem aproksymacji $O (log 2 n)$ , gdzie $n$ jest liczbą wierzchołków. Zminimalizowanie jednostronicowej lub dwustronicowej liczby przecięć jest wykonalne przy stałym parametrze , gdy jest sparametryzowane przez liczbę cykliczną danego wykresu lub przez kombinację liczby przecięć i szerokości drzewa wykresu. Opracowano również heurystyczne metody zmniejszania złożoności przecinania, oparte np. na starannej kolejności wstawiania wierzchołków i lokalnej optymalizacji .

Dwustronicowe osadzenie książki ze stałym podziałem krawędzi na strony można interpretować jako formę planarności klastrowej , w której dany graf musi być narysowany w taki sposób, aby części grafu (dwa podzbiory krawędzi) były umieszczone na rysunku w sposób odzwierciedlający ich grupowanie. Osadzanie dwustronicowej książki zostało również wykorzystane do znalezienia równoczesnych osadzeń grafów, w których dwa grafy są podane w tym samym zestawie wierzchołków i trzeba znaleźć miejsce dla wierzchołków, w których oba grafy są narysowane planarnie z prostymi krawędziami.

Osadzone książki z więcej niż dwiema stronami były również używane do konstruowania trójwymiarowych rysunków wykresów. W szczególności Wood (2002) zastosował konstrukcję osadzania książek, która utrzymuje niski stopień każdego wierzchołka na każdej stronie, jako część metody osadzania wykresów w trójwymiarowej siatce o małej objętości.

fałdowanie RNA

Fragment ludzkiej telomerazy przedstawiający pseudowęzeł . Jeśli fragment zostanie rozciągnięty prosto wzdłuż grzbietu osadzonej książki, niebieskie pary zasad można narysować w dwóch nie krzyżujących się podzbiorach powyżej i poniżej grzbietu, co pokazuje, że ten pseudowęzeł tworzy strukturę dwuwtórną.

W badaniu tego, jak cząsteczki RNA fałdują się, tworząc swoją strukturę, standardową postać drugorzędowej struktury kwasu nukleinowego można opisać schematycznie jako łańcuch zasad (sama sekwencja RNA), narysowany wzdłuż linii wraz ze zbiorem łuków nad linia opisująca pary zasad struktury. Oznacza to, że chociaż te struktury mają w rzeczywistości skomplikowany trójwymiarowy kształt, ich łączność (gdy istnieje struktura drugorzędna) można opisać za pomocą bardziej abstrakcyjnej struktury, osadzania jednej strony w książce. Jednak nie wszystkie fałdy RNA zachowują się w ten prosty sposób. Haslinger i Stadler (1999) zaproponowali tak zwaną „strukturę dwudrugorzędową” dla niektórych pseudowęzłów RNA , która przybiera formę osadzania dwustronicowej książki: sekwencja RNA jest ponownie rysowana wzdłuż linii, ale pary zasad są rysowane jako łuki zarówno powyżej, jak i poniżej tej linii. Aby utworzyć strukturę dwudrugorzędową, graf musi mieć maksymalny stopień co najwyżej trzy: każda podstawa może uczestniczyć tylko w jednym łuku diagramu, oprócz dwóch połączeń z sąsiadami w sekwencji podstawowej. Zaletą tego sformułowania jest fakt, że wyklucza on struktury, które są faktycznie zawiązane w przestrzeni i że pasuje do większości znanych pseudowęzłów RNA.

Ponieważ uporządkowanie kręgosłupa jest znane z góry dla tego zastosowania, testowanie istnienia struktury bi-drugorzędowej dla danego parowania zasad jest proste. Problem przypisania krawędzi dwóm stronom w sposób zgodny można sformułować jako przypadek spełnialności 2 lub jako problem testowania dwudzielności wykresu kołowego , którego wierzchołkami są pary zasad, a krawędzie opisują skrzyżowania między parami zasad. Alternatywnie i wydajniej, jak Haslinger i Stadler (1999) , struktura bi-drugorzędowa istnieje wtedy i tylko wtedy, gdy wykres diagramu wejściowego (wykres utworzony przez połączenie zasad w cykl w ich kolejności sekwencji i dodanie danych par zasad jako krawędzie) jest grafem planarnym . Ta charakterystyka umożliwia rozpoznanie struktur bi-drugorzędowych w czasie liniowym jako przykład testowania planarności .

Blin i in. (2007) wykorzystali związek między strukturami drugorzędowymi a osadzonymi książkami jako część dowodu na NP-twardość niektórych problemów w porównywaniu struktur drugorzędowych RNA. A jeśli struktura RNA jest raczej trzeciorzędowa niż dwudrugorzędowa (to znaczy, jeśli wymaga więcej niż dwóch stron na swoim diagramie), to określenie numeru strony jest ponownie NP-trudne.

Teoria złożoności obliczeniowej

Pavan, Tewari i Vinodchandran (2012) wykorzystali osadzanie książek do badania teorii złożoności obliczeniowej problemu osiągalności w grafach skierowanych . Jak zaobserwowali, osiągalność dwustronicowych grafów skierowanych można rozwiązać w jednoznacznej przestrzeni logarytmicznej (odpowiednik, dla złożoności przestrzeni logarytmicznej , klasy UP jednoznacznych problemów wielomianowych). Jednak osiągalność trzystronicowych grafów skierowanych wymaga pełnej mocy niedeterministycznej przestrzeni logarytmicznej . Zatem osadzenia w książkach wydają się być ściśle związane z rozróżnieniem między tymi dwiema klasami złożoności.

Istnienie grafów ekspandera ze stałą liczbą stron jest kluczowym krokiem w udowodnieniu, że nie ma symulacji w czasie subkwadratowym dwutaśmowych niedeterministycznych maszyn Turinga przez jednotaśmowe niedeterministyczne maszyny Turinga.

Inne dziedziny matematyki

McKenzie i Overbay (2010) badają zastosowania grubości książki w algebrze abstrakcyjnej , używając grafów zdefiniowanych na podstawie dzielników zera skończonego lokalnego pierścienia , tworząc wierzchołek dla każdego dzielnika zera i krawędź dla każdej pary wartości, których iloczyn wynosi zero.

W serii wielu artykułów Dynnikov przestudiował topologiczne wiązania węzłów i połączeń , wykazując, że te osadzenia można opisać kombinatoryczną sekwencją symboli i że topologiczną równoważność dwóch połączeń można wykazać za pomocą sekwencji lokalnych zmian w osadzania.