Original title:
Algebraické, strukturální a výpočetní vlastnosti geometrických reprezentací grafů
Translated title:
Algebraic, Structural, and Complexity Aspects of Geometric Representations of Graphs
Authors:
Zeman, Peter ; Klavík, Pavel (advisor) ; Nešetřil, Jaroslav (referee) Document type: Master’s theses
Year:
2016
Language:
eng Abstract:
Title: Algebraic, Structural and Complexity Aspects of Geometric Representations of Graphs Author: Peter Zeman Department: Computer Science Institute Supervisor: RNDr. Pavel Klavík Supervisor's e-mail: klavik@iuuk.mff.cuni.cz Keywords: automorphism groups, interval graphs, circle graphs, comparability graphs, H-graphs, recognition, dominating set, graph isomorphism, maximum clique, coloring Abstract: We study symmetries of geometrically represented graphs. We describe a tech- nique to determine the automorphism group of a geometrically represented graph, by understanding the structure of the induced action on all geometric representations. We prove that interval graphs have the same automorphism groups as trees, and for a given interval graph, we construct a tree with the same automorphism group which answers a question of Hanlon [Trans. Amer. Math. Soc 272(2), 1982]. For permutation and circle graphs, we give an inductive characterization by semidirect and wreath prod- ucts. We also prove that every abstract group can be realized by the automorphism group of a comparability graph/poset of the dimension at most four. We also study H-graphs, introduced by Biró, Hujter, and Tuza in 1992. Those are intersection graphs of connected subgraphs of a subdivision of a graph H. This thesis is the first comprehensive...
Keywords:
automorphism groups; geometric representations of graphs; intersection representations; partial representation extension; geometrické reprezentace grafů; grupy automorfismů; průnikové reprezentace; rozšiřování částečných reprezentací
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/83134