Seminarium magisterskie I [1000-I2SEMmgrI] Semestr letni 2024/25
Seminarium, grupa nr 5

Podstawy:

1. Xiaxia GUAN1, Chuxiong WU1, Weihua YANG1, Jixiang MENG; A survey on book-embedding of planar graphs; Front. Math. China 2022, 17(2): 255–273 (2022)

2. Mustafa Alhashem, Guy-Vincent Jourdan, Nejib Zaguia, University of Ottawa; On the book embedding of ordered sets, January 2015; Ars Combinatoria 119:47-64

3. Kwiatkowska A B. On page number of N-free posets. In: Fifth Cracow Conference on Graph Theory USTRON ’06, Electron. Notes Discrete Math., Vol. 24, Amsterdam: Elsevier Sci. B. V., 2006, 243–249

4. Bernhart F., Kainen P.C., The book thickness of a graph, J. Combin. Theory

B 27(1979), 320-321.

5. Garg A., Tamassia R., Upward planarity testing, Order 12(1995), 109-133.

6. Nowakowski R., Parker A., Ordered sets, pagenumbers and planarity, Order

6(1989), 209-218.

Pozostała literatura będzie dobrana w zależności od przyjętych kierunków badawczych w pracach magisterskich.

Seminarium będzie poświęcone zagadnieniom teoretyczno-algorytmicznym z zakresu Teorii Grafów.

Rozważane będą problemy teoretyczne o szerokich zastosowaniach i wpływie na optymalizację funkcjonowania technologii cyfrowej, np. układów VLSI, głównie z obszarów teroretycznych tj.:

- grafy planarne,

- posety planarne i własności ich reprezentacji płaskich,

- posety N-wolne i szeregowo-równoległe.

Rozważaniom teoretycznym będzie towarzyszyłam implementacja związanych z nimi algorytmów.

Główne kierunki badań to:

- oszacowania dla posetów płaskich (planarnych),

- przykłady braku oszacowania,

- wykorzystanie rezultatów dla posetów N-wolnych w posetach, które zawierają np. ograniczoną liczbę N-ek.

Dopuszczalne jest wybranie innej tematyki z Teorii Grafów po dokładnym uzasadnieniu metodyki badawczo-poszukiwawczej.

- elementy standardowych zajęć wykładowych (podstawy niezbędne do pracy z wybranym tematem),

- konwersatoria w obrębie całej grupy,

- prezentacja zainteresowań teoretyczno-informatycznych uczestników grupy,

- dyskusja oraz postawienie problemu każdemu z uczestników grupy,

- samodzielna praca nad zadanymi materiałami i przypisanymi problemami (analiza i opracowanie tekstu, projektowanie i praca nad kodami źródłowymi programów),

- referaty studentów dotyczące wybranych zagadnień w oparciu o publikacje naukowe,

- referaty studentów dotyczące postępów prac (zadana tematyki i postęp prac)

- wykonanie innych zadań w zależności od tematyki pracy

Warunkami koniecznymi do zaliczenia seminarium w semestrze letnim będą:

- obecność na zajęciach,

- wygłoszenie co najmniej dwóch referatów

- ustalenie tematyki pracy magisterskiej i opracowanie jej wstępnego planu.

4inf