Umieszczanie zbiorów częściowo uporządkowanych w książce o minimalnej liczbie stron

Umieszczenie grafu w książce jest definiowane przez kolejność jego wierzchołków na grzbiecie książki i przyporządkowanie jego krawędzi stronom książki tak, aby na żadnej stronie krawędzie nie przecinały się. Umieszczenie zbioru częściowo uporządkowanego (posetu) P w książce polega na umieszczeniu jego digrafu pokrycia (diagramu Hassego), z elementami zbioru P na grzbiecie tworzącymi rozszerzenie liniowe zbioru P. Problemem jest umieszczenie posetu P na możliwie najmniejszej liczbie stron. Problem liczby stron dla posetów wydaje się być znacznie trudniejszy niż dla grafów. Na dwóch stronach można umieścić graf planarny, który jest podgrafem hamiltonowskiego grafu planarnego, natomiast nie jest znana charakteryzacja posetów dających się umieści na dwóch stronach. Ponadto, każdy graf planarny można umieścić na co najwyżej czterech stronach, natomiast przypuszcza się, ze w przypadku posetów planarnych liczba stron nie jest ograniczona. Wyniki w pracy dotyczą tych dwóch problemów. W Rozdziale 4 zamieszczono algorytm do umieszczania posetów drzewiastych na jednej stronie, który tworzy ramy dla algorytmów umieszczania posetów o rozbudowanej strukturze drzewiastej. W Rozdziale 5 rozważa się klasę posetów planarnych, w których każdy blok jest cyklem. Mimo swej prostoty, dwie strony nie wystarczają do ich umieszczenia. Każdy taki poset może być umieszczony na trzech stronach i trzy strony czasem są niezbędne. Najobszerniejsza cześć pracy stanowią Rozdziały 6 i 7, poświęcone posetom N-wolnym, pojawiającym się w wielu obszarach badan nad posetami. Rozważania w tych Rozdziałach bazują na podejściu teorio-grafowym, w którym digraf pokrycia posetu N-wolnego jest interpretowany jako digraf łukowy. Podano wzór na liczbę stron dla posetów N-wolnych o strukturze drzewiastej, oszacowano liczbę stron dla dowolnego posetu N-wolnego i przedstawiono algorytm umieszczania w książce dowolnych posetów, bazujący na przekształceniu posetu do posetu N-wolnego. W Rozdziale 7 są rozważane posety planarne. Podano lokalne warunki konieczne na to, aby N-wolny poset był planarny, skąd wywnioskowano, ze N-wolne posety planarne o strukturze drzewiastej można umieścić na dwóch stronach. Ta cześć pracy zawiera najważniejszy wynik pracy, ze N-wolny poset planarny, reprezentowany przez swój do góry płaski digraf pokrycia, można umieścić na dwóch stronach. Jako dowód tego twierdzenia przedstawiono algorytm o złożoności wielomianowej i udowodniono jego poprawność. Rozważania dotyczące posetów są prowadzone w języku (di)grafów z nimi związanych oraz z wykorzystaniem technik dowodzenia i konstrukcji algorytmicznych pochodzących z teorii grafów. Niektóre wyniki były prezentowane na kilku konferencjach [39], [41], [42]. MCS 2010: 05C10, 5C62, 05C76, 05C85, 06Axx, 06A06, 06A07, 68Q25 ACM CCS: 6.2.1, 6.2.2 Słowa kluczowe: zbiór częściowo uporządkowany (poset), digraf, zbiór i digraf N-wolny, zbiór i digraf planarny, drzewo, umieszczanie posetów w książce

In this Thesis we deal with the book embedding problem for partially ordered sets (posets). A book embedding of a graph G consists of two assignments: the vertices of G to the spine of a book in some order and the edges of G to the pages of the book so that the edges on the same page do not intersect. In a book embedding of a poset (P; ), the covering digraph (the Hasse diagram) of P is embedded with the elements of P on the spine as a linear extension of P. The objective is to minimize the number of pages used. The page number problem for posets seems to be more challenging and difficult than for graphs. It is known that the page number equals 2 for planar graphs which are subgraphs of Hamiltonian planar graphs, but no characterization of 2-page posets is known. Moreover, each planar graph can be embedded in 4 pages and it is conjectured that the page number for planar posets is unbounded. We focus in the Thesis on these two problems. In Section 4, an algorithm for 1-page embedding of tree-posets is presented which in the next sections is extended to run for several tree-structured posets. In Section 5, one such family of planar posets – tree-combinations of cycles – is introduced. Despite the simplicity of such posets, it is shown that in general they need 3 pages. In Sections 6 and 7, which are the main parts of the Thesis, the page number problem is considered in the family of N-free posets. Such posets have been recently investigated in the connection with various problems on graphs, digraphs, and posets. Our approach is based on the interpretation of covering digraphs of N-free posets as line digraphs. The page number is determined exactly for tree-structured N-free posets and some bounds are provided for arbitrary N-free posets. Moreover a book embedding algorithm is presented for arbitrary posets which is based on transformation of posets to N-free posets. In Section 7, our attention is focused on planar posets. Necessary conditions for an N-free poset to be planar are formulated and as a consequence we show that the page number of tree-structured N-free planar posets equals 2. Then we present the main result of the Thesis which states that any N-free planar poset given as its upward plane representation (drawing) can be embedded into 2 pages. The proof of this result is fully constructive – we provide a polynomial time algorithm for such embeddings. The investigations in this Thesis are carried on in the language and terms of graphs and digraphs related to posets and we use proof and algorithmic techniques from graph theory. Some of the results were presented at combinatorial meetings [39], [41], [42]. MCS 2010: 05C10, 5C62, 05C76, 05C85, 06Axx, 06A06, 06A07, 68Q25 ACM CCS: 6.2.1, 6.2.2 Key words: partially ordered set (poset), digraph, N-free digraph and poset, planar digraph and poset, tree, page number of graphs, digraphs, and posets