Original title:
Grupy symetrií grafů
Translated title:
Groups of automorphisms of graphs
Authors:
Zeman, Peter ; Nedela, Roman (advisor) ; Felsner, Stefan (referee) ; Širáň, Jozef (referee) Document type: Doctoral theses
Year:
2022
Language:
eng Abstract:
[eng][cze] Groups of automorphisms of graphs - abstract In this thesis we investigate automorphism groups of several restricted classes of graphs from structural and computational point of view. For interval, permutation, circle, and planar graphs we give inductive characterizations of their automorphism groups in terms of group products. For chordal graphs of bounded leafage, prove that computing the automorphism group, and consequently the isomorphism problem, is fixed parameter tractable. For maps on surfaces, we give a linear time algorithm computing the automor- phism group, parametrized by the genus of the underlying surface. 1Groups of automorphisms of graphs - abstrakt V tejto práci skúmame grupy automorfizmov špecifických tried grafov z štrukturál- neho a výpočetného hladiska. Pre intervalové, permutačné, tetivové a rovinné grafy sme odvodili induktívnu charakterizáciu grúp automorfizmov pomocou grupových súčinov. Pre chordálne grafy s ohraničenou listnatosťou sme dokázali, že problémy výpočtu grupy automorfizmov a testovania izomorfizmu sú fixed parameter tractable. Pre mapy na plochách sme popísali lineárny algoritmus, ktorý počíta grupu automorfizmov mapy na ploche s pevným rodom. 1
Keywords:
Graph|group|automorphism|algorithm|complexity; Graf|grupa|automorfizmus|algoritmus|složitost
Institution: Charles University Faculties (theses)
(web)
Document availability information: Available in the Charles University Digital Repository. Original record: http://hdl.handle.net/20.500.11956/173835