Search

Circle graphs are intersection graphs of chords of a circle. In this paper, we present a new algorithm for the circle graph isomorphism problem running in time $O((n+m)\alpha(n+m))$ where $n$ is the number of vertices, $m$ is the number of edges and $\alpha$ is the inverse Ackermann function. Our algorithm is based on the minimal split decomposition [Cunnigham, 1982] and uses the state-of-art circle graph recognition algorithm [Gioan, Paul, Tedder, Corneil, 2014] in the same running time. It improves the running time $O(nm)$ of the previous algorithm [Hsu, 1995] based on a similar approach.

Extension Properties of Graphs and Structures Pavel Klavík The main motivation for graph drawing and geometric representations is finding ways to visualize graphs efficiently to make their structure as understandable as possible. In this thesis, we are concerned with structural properties which are implied for graphs having certain geometric representations. We study two types of geometric representations: inter- section representations in which the vertices are represented by geometric sets while the edges are encoded by their intersections, and planar embeddings of planar graphs which are drawing of graphs into the plane without crossing edges. The existence of geometric representations can be used to deduce additional information about graphs. The main idea of this thesis is to ask what extra information can be deduced from the structure of all possible geometric representations. In Part I, we study the partial representation extension problems for intersection rep- resentations. Aside from the graph, the input also gives a partial representation, which prescribes a representation of an induced subgraph. We ask whether this partial repre- sentation can be extended to a full representation of the input graph without altering the predrawn sets. I introduced this problem in 2010 in my Bachelor's thesis. We...

We describe a technique to determine the automorphism group of a geometrically represented graph, by understanding the structure of the induced action on all geometric representations. Using this, we characterize automorphism groups of interval, permutation and circle graphs. We combine techniques from group theory (products, homomorphisms, actions) with data structures from computer science (PQ-trees, split trees, modular trees) that encode 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 products. 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.

Comparability graphs are graphs which have transitive orientations. The dimension of a poset is the least number of linear orders whose intersection gives this poset. The dimension ${\rm dim}(X)$ of a comparability graph $X$ is the dimension of any transitive orientation of X, and by $k$-DIM we denote the class of comparability graphs $X$ with ${\rm dim}(X) \le k$. It is known that the complements of comparability graphs are exactly function graphs and permutation graphs equal 2-DIM. In this paper, we characterize the automorphism groups of permutation graphs similarly to Jordan's characterization for trees (1869). For permutation graphs, there is an extra operation, so there are some extra groups not realized by trees. For $k \ge 4$, we show that every finite group can be realized as the automorphism group of some graph in $k$-DIM, and testing graph isomorphism for $k$-DIM is GI-complete.

A graph $G$ covers a graph $H$ if there exists a locally bijective homomorphism from $G$ to $H$. We deal with regular covers in which this locally bijective homomorphism is prescribed by an action of a subgroup of ${\rm Aut}(G)$. Regular covers have many applications in constructions and studies of big objects all over mathematics and computer science. We study computational aspects of regular covers that have not been addressed before. The decision problem RegularCover asks for two given graphs $G$ and $H$ whether $G$ regularly covers $H$. When $|H|=1$, this problem becomes Cayley graph recognition for which the complexity is still unresolved. Another special case arises for $|G| = |H|$ when it becomes the graph isomorphism problem. Therefore, we restrict ourselves to graph classes with polynomially solvable graph isomorphism. Inspired by Negami, we apply the structural results used by Babai in the 1970's to study automorphism groups of graphs. Our main result is the following FPT meta-algorithm: Let $\cal C$ be a class of graphs such that the structure of automorphism groups of 3-connected graphs in $\cal C$ is simple. Then we can solve RegularCover for $\cal C$-inputs $G$ in time $O^*(2^{e(H)/2})$ where $e(H)$ denotes the number of the edges of $H$. As one example of $\cal C$, this meta-algorithm applies to planar graphs. In comparison, testing general graph covers is known to be NP-complete for planar inputs $G$ even for small fixed graphs $H$ such as $K_4$ or $K_5$. Most of our results also apply to general graphs, in particular the complete structural understanding of regular covers for 2-cuts., Comment: The conference version accepted to ICALP 2014

The partial representation extension problem is a recently introduced generalization of the recognition problem. A circle graph is an intersection graph of chords of a circle. We study the partial representation extension problem for circle graphs, where the input consists of a graph g and a partial representation \(\mathcal{r'}\) giving some pre-drawn chords that represent an induced subgraph of g. The question is whether one can extend \(\mathcal{r'}\) to a representation \(\mathcal{r}\) of the entire g, i.e., whether one can draw the remaining chords into a partially pre-drawn representation.our main result is a polynomial-time algorithm for partial representation extension of circle graphs. To show this, we describe the structure of all representation a circle graph based on split decomposition. This can be of an independent interest.keywordsintersection graphinterval graphchordal graphprime graphcircle graphthese keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

Klavik et al. [arXiv:1207.6960] recently introduced a generalization of recognition called the bounded representation problem which we study for the classes of interval and proper interval graphs. The input gives a graph G and in addition for each vertex v two intervals L_v and R_v called bounds. We ask whether there exists a bounded representation in which each interval I_v has its left endpoint in L_v and its right endpoint in R_v. We show that the problem can be solved in linear time for interval graphs and in quadratic time for proper interval graphs. Robert's Theorem states that the classes of proper interval graphs and unit interval graphs are equal. Surprisingly the bounded representation problem is polynomially solvable for proper interval graphs and NP-complete for unit interval graphs [Klav\'{\i}k et al., arxiv:1207.6960]. So unless P = NP, the proper and unit interval representations behave very differently. The bounded representation problem belongs to a wider class of restricted representation problems. These problems are generalizations of the well-understood recognition problem, and they ask whether there exists a representation of G satisfying some additional constraints. The bounded representation problems generalize many of these problems.

In this thesis, we study geometric intersection representations of graphs. For a fixed class, the well-known recognition problem asks whether a given graph belongs to this class. We study a generalization of this problem called partial representation extension. Its input consists of a graph with a partial representation, so a part of the graph is pre-drawn. The problems asks whether this partial representation can be extended to a representation of the entire graph. We study this problem for classes of interval graphs, proper interval graphs, unit interval graphs and chordal graphs (in the setting of subtrees-in-tree representations). We give linear-time algorithms for the first two classes and an almost quadratic-time algorithm for unit interval graphs. For chordal graphs, we consider different versions of the problem and show that almost all cases are NP-complete. Even though the classes of proper and unit interval graphs are known to be equal, the partial representation extension problem distinguishes them. For unit interval graphs, it poses additional restrictions concerning precise positions of intervals, and we describe a new structure of unit interval representations to deal with this. 1

We study the computational complexity of graph planarization via edge contraction. The problem CONTRACT asks whether there exists a set $S$ of at most $k$ edges that when contracted produces a planar graph. We work with a more general problem called $P$-RESTRICTEDCONTRACT in which $S$, in addition, is required to satisfy a fixed MSOL formula $P(S,G)$. We give an FPT algorithm in time $O(n^2 f(k))$ which solves $P$-RESTRICTEDCONTRACT, where $P(S,G)$ is (i) inclusion-closed and (ii) inert contraction-closed (where inert edges are the edges non-incident to any inclusion minimal solution $S$). As a specific example, we can solve the $\ell$-subgraph contractibility problem in which the edges of a set $S$ are required to form disjoint connected subgraphs of size at most $\ell$. This problem can be solved in time $O(n^2 f'(k,\ell))$ using the general algorithm. We also show that for $\ell \ge 2$ the problem is NP-complete.

The problem Cover(H) asks whether an input graph G covers a fixed graph H (i.e., whether there exists a homomorphism G to H which locally preserves the structure of the graphs). Complexity of this problem has been intensively studied. In this paper, we consider the problem PlanarCover(H) which restricts the input graph G to be planar. PlanarCover(H) is polynomially solvable if Cover(H) belongs to P, and it is even trivially solvable if H has no planar cover. Thus the interesting cases are when H admits a planar cover, but Cover(H) is NP-complete. This also relates the problem to the long-standing Negami Conjecture which aims to describe all graphs having a planar cover. Kratochvil asked whether there are non-trivial graphs for which Cover(H) is NP-complete but PlanarCover(H) belongs to P. We examine the first nontrivial cases of graphs H for which Cover(H) is NP-complete and which admit a planar cover. We prove NP-completeness of PlanarCover(H) in these cases., Comment: Full version (including Appendix) of a paper from the conference WG 2011

Intersection graphs are a well studied field of graph theory. Complexity questions of recognition have been studied for several years. Given a graph, we ask whether the graph belongs to a fixed class. In this thesis, we introduce a new problem of partial representation extension. In this problem, aside from a graph, a part of a representation is also fixed. We ask whether it is possible to extend this partial representation to the whole graph. This problem is at least as hard as recognition. We study the partial representation extension problem for several intersection defined classes. We solve extending of interval graphs in time O(n2) and proper interval graphs in time O(mn). Using an approach described by Golumbic, we further show that comparability and permutation graphs are extendable in time O( · m). There are some classes that are known to be equal, for example unit interval graphs and proper interval graphs. Surprisingly, in the case of extending, we need to distinguish them. Similarly, we show that extending of function graphs and extending of co-comparability graphs are completely different problems.

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...

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