BZPEERPapers, people, evidence and research pathsDiscover
Research tools
Network
Opportunities
Account
Source author record
Pavel Klavík appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.
Catalog footprint
Research graph
Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.
BZPEER is loading the nearby papers, people, topics and institutions for this page.
Published work
We investigate automorphism groups of planar graphs. The main result is a complete recursive description of all abstract groups that can be realized as automorphism groups of planar graphs. The characterization is formulated in terms of inhomogeneous wreath products. In the proof, we combine techniques from combinatorics, group theory, and geometry. This significantly improves the Babai's description (1975).
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.
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.
Interval graphs are intersection graphs of closed intervals. A generalization of recognition called partial representation extension was introduced recently. The input gives an interval graph with a partial representation specifying some pre-drawn intervals. We ask whether the remaining intervals can be added to create an extending representation. Two linear-time algorithms are known for solving this problem. In this paper, we characterize the minimal obstructions which make partial representations non-extendible. This generalizes Lekkerkerker and Boland's characterization of the minimal forbidden induced subgraphs of interval graphs. Each minimal obstruction consists of a forbidden induced subgraph together with at most four pre-drawn intervals. A Helly-type result follows: A partial representation is extendible if and only if every quadruple of pre-drawn intervals is extendible by itself. Our characterization leads to a linear-time certifying algorithm for partial representation extension.
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.
Power awareness is fast becoming immensely important in computing, ranging from the traditional High Performance Computing applications, to the new generation of data centric workloads. In this work we describe our efforts towards a power efficient computing paradigm that combines low precision and high precision arithmetic. We showcase our ideas for the widely used kernel of solving systems of linear equations that finds numerous applications in scientific and engineering disciplines as well as in large scale data analytics, statistics and machine learning. Towards this goal we developed tools for the seamless power profiling of applications at a fine grain level. In addition, we verify here previous work on post FLOPS/Watt metrics and show that these can shed much more light in the power/energy profile of important applications.
Interval graphs are intersection graphs of closed intervals of the real-line. The well-known computational problem, called recognition, asks whether an input graph $G$ can be represented by closed intervals, i.e., whether $G$ is an interval graph. There are several linear-time algorithms known for recognizing interval graphs, the oldest one is by Booth and Lueker [J. Comput. System Sci., 13 (1976)] based on PQ-trees. In this paper, we study a generalization of recognition, called partial representation extension. The input of this problem consists of a graph $G$ with a partial representation $\cal R'$ fixing the positions of some intervals. The problem asks whether it is possible to place the remaining interval and create an interval representation $\cal R$ of the entire graph $G$ extending $\cal R'$. We generalize the characterization of interval graphs by Fulkerson and Gross [Pac. J. Math., 15 (1965)] to extendible partial representations. Using it, we give a linear-time algorithm for partial representation extension based on a reordering problem of PQ-trees.
The recently introduced problem of extending partial interval representations asks, for an interval graph with some intervals pre-drawn by the input, whether the partial representation can be extended to a representation of the entire graph. In this paper, we give a linear-time algorithm for extending proper interval representations and an almost quadratic-time algorithm for extending unit interval representations. We also introduce the more general problem of bounded representations of unit interval graphs, where the input constrains the positions of some intervals by lower and upper bounds. We show that this problem is NP-complete for disconnected input graphs and give a polynomial-time algorithm for the special class of instances, where the ordering of the connected components of the input graph along the real line is prescribed. This includes the case of partial representation extension. The hardness result sharply contrasts the recent polynomial-time algorithm for bounded representations of proper interval graphs [Balko et al. ISAAC'13]. So unless $\text{P} = \text{NP}$, proper and unit interval representations have vastly different structure. This explains why partial representation extension problems for these different types of representations require substantially different techniques.
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\'ı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.
Function graphs are graphs representable by intersections of continuous real-valued functions on the interval [0,1] and are known to be exactly the complements of comparability graphs. As such they are recognizable in polynomial time. Function graphs generalize permutation graphs, which arise when all functions considered are linear. We focus on the problem of extending partial representations, which generalizes the recognition problem. We observe that for permutation graphs an easy extension of Golumbic's comparability graph recognition algorithm can be exploited. This approach fails for function graphs. Nevertheless, we present a polynomial-time algorithm for extending a partial representation of a graph by functions defined on the entire interval [0,1] provided for some of the vertices. On the other hand, we show that if a partial representation consists of functions defined on subintervals of [0,1], then the problem of extending this representation to functions on the entire interval [0,1] becomes 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.