|
|
Groups of automorphisms of graphs
Zeman, Peter ; Nedela, Roman (advisor) ; Felsner, Stefan (referee) ; Širáň, Jozef (referee)
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. 1
|
|
|
Algebraic, Structural, and Complexity Aspects of Geometric Representations of Graphs
Zeman, Peter ; Klavík, Pavel (advisor) ; Nešetřil, Jaroslav (referee)
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...
|
|
|
Automorphism Groups of Geometrically Represented Graphs
Zeman, Peter ; Klavík, Pavel (advisor) ; Nedela, Roman (referee)
In this thesis, we are interested in automorphism groups of classes of graphs with a very strong structure. Probably the first nontrivial result in this direction is from 1869 due to Jordan. He gave a characterization of the class T of the automorphism groups of trees. Surprisingly, automorphism groups of intersection-defined classes of graphs were studied only briefly. Even for deeply studied classes of intersection graphs the structure of their automorphism groups is not well known. We study the problem of reconstruct- ing the automorphism group of a geometric intersection graph from a good knowledge of the structure of its representations. We mainly deal with interval graphs. Interval graphs are intersection graphs of intervals on the real line. They are one of the oldest and most studied classes of geometric intersection graphs. Our main result is that the class T is the same as the class I of the automorphism groups of interval graphs. Moreover, we show for an interval graph how to find a tree with the same automorphism group, and vice versa. 1
|
|
|
Speciální třídy P-matic v intervalovém prostředí
Lorenc, Matyáš ; Hladík, Milan (advisor) ; Zeman, Peter (referee)
This work focuses on generalizing some easily recognizable subclasses of P-matrices into interval settings, including some results regarding these classes. Those classes are those of B-matrices, doubly B-matrices and BR π -matrices. We derive characterizations, some necessary conditions and sufficient ones, plus we introduce some of their properties, such as are the closure ones and a few conditions the entries of such matrices satisfy. Then we proceed to state a way to generate instances of some of these interval matrix classes. 1
|
|
|
Circle packing and Möbius transformations
Porvichová, Janka ; Zeman, Peter (advisor) ; Kratochvíl, Jan (referee)
A graph can be represented by various geometric representations. In this work we focus on the circle packing representation. We state various concepts impor- tant for proving results regarding this kind of representation. We introduce a known proof of existence of a circle packing for planar graphs and a proof of existence of a primal-dual circle packing for 3-connected graphs. Next, we focus on computational complexity of extending the representation for a given partial circle packing. We examine the proof of the theorem stating that deciding whet- her such an extension exists is an NP-hard problem. We introduce our theoretical algorithm for extension construction based on real RAM machine. 1
|
|
|
Algebraic, Structural, and Complexity Aspects of Geometric Representations of Graphs
Zeman, Peter ; Klavík, Pavel (advisor) ; Nešetřil, Jaroslav (referee)
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...
|
|
|
Automorphism Groups of Geometrically Represented Graphs
Zeman, Peter ; Klavík, Pavel (advisor) ; Nedela, Roman (referee)
In this thesis, we are interested in automorphism groups of classes of graphs with a very strong structure. Probably the first nontrivial result in this direction is from 1869 due to Jordan. He gave a characterization of the class T of the automorphism groups of trees. Surprisingly, automorphism groups of intersection-defined classes of graphs were studied only briefly. Even for deeply studied classes of intersection graphs the structure of their automorphism groups is not well known. We study the problem of reconstruct- ing the automorphism group of a geometric intersection graph from a good knowledge of the structure of its representations. We mainly deal with interval graphs. Interval graphs are intersection graphs of intervals on the real line. They are one of the oldest and most studied classes of geometric intersection graphs. Our main result is that the class T is the same as the class I of the automorphism groups of interval graphs. Moreover, we show for an interval graph how to find a tree with the same automorphism group, and vice versa. 1
|
guest ::
