19 citations · 63 across the 12 of their papers we have counts for
20 papers
Circle Graph Isomorphism in Almost Linear Time
Vít Kalisz, Pavel Klavík, Peter Zeman
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 whe…
Algorithmic Aspects of Regular Graph Covers
Jiří Fiala, Pavel Klavík, Jan Kratochvíl +1
A graph covers a graph if there exists a locally bijective homomorphism from to . We deal with regular covers where this homomorphism is prescribed by the action of…
Cops and Robbers on Intersection Graphs
Tomáš Gavenčiak, Przemysław Gordinowicz, Vít Jelínek +2
The cop number of a graph is the smallest such that cops win the game of cops and robber on . We investigate the maximum cop number of geometric intersection graphs,…
Graph Isomorphism Restricted by Lists
Pavel Klavik, Dušan Knop, Peter Zeman
The complexity of graph isomorphism (GraphIso) is a famous unresolved problem in theoretical computer science. For graphs and , it asks whether they are the same up to a rel…
On the Classes of Interval Graphs of Limited Nesting and Count of Lengths
Pavel Klavík, Yota Otachi, Jiří Šejnoha
In 1969, Roberts introduced proper and unit interval graphs and proved that these classes are equal. Natural generalizations of unit interval graphs called -length interval grap…
Automorphism Groups of Comparability Graphs
Pavel Klavík, Peter Zeman
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…
Jordan-like characterization of automorphism groups of planar graphs
Pavel Klavík, Roman Nedela, Peter Zeman
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 plana…
3-connected Reduction for Regular Graph Covers
Jiří Fiala, Pavel Klavík, Jan Kratochvíl +1
A graph covers a graph if there exists a locally bijective homomorphism from to . We deal with regular coverings in which this homomorphism is prescribed by an actio…
Automorphism Groups of Geometrically Represented Graphs
Pavel Klavík, Peter Zeman
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 representati…
Minimal Obstructions for Partial Representations of Interval Graphs
Pavel Klavík, Maria Saumell
Interval graphs are intersection graphs of closed intervals. A generalization of recognition called partial representation extension was introduced recently. The input gives an int…
Changing Computing Paradigms Towards Power Efficiency
Pavel Klavík, A. Cristiano I. Malossi, Constantin Bekas +1
Power awareness is fast becoming immensely important in computing, ranging from the traditional High Performance Computing applications, to the new generation of data centric workl…
Algorithmic Aspects of Regular Graph Covers with Applications to Planar Graphs
Jiří Fiala, Pavel Klavík, Jan Kratochvíl +1
A graph covers a graph if there exists a locally bijective homomorphism from to . We deal with regular covers in which this locally bijective homomorphism is prescri…
Bounded Representations of Interval and Proper Interval Graphs
Martin Balko, Pavel Klavík, Yota Otachi
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…
Extending Partial Representations of Circle Graphs
Steven Chaplick, Radoslav Fulek, Pavel Klavík
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 s…
Extending Partial Representations of Interval Graphs
Pavel Klavík, Jan Kratochvíl, Yota Otachi +2
Interval graphs are intersection graphs of closed intervals of the real-line. The well-known computational problem, called recognition, asks whether an input graph can be repre…
Extending Partial Representations of Proper and Unit Interval Graphs
Pavel Klavík, Jan Kratochvíl, Yota Otachi +4
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 representa…
Extending Partial Representations of Subclasses of Chordal Graphs
Pavel Klavik, Jan Kratochvil, Yota Otachi +1
Chordal graphs are intersection graphs of subtrees of a tree T. We investigate the complexity of the partial representation extension problem for chordal graphs. A partial represen…
Extending partial representations of function graphs and permutation graphs
Pavel Klavík, Jan Kratochvíl, Tomasz Krawczyk +1
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 gra…
MSOL Restricted Contractibility to Planar Graphs
James Abello, Pavel Klavík, Jan Kratochvíl +1
We study the computational complexity of graph planarization via edge contraction. The problem CONTRACT asks whether there exists a set of at most edges that when contracte…
On the Complexity of Planar Covering of Small Graphs
Ondřej Bílka, Jozef Jirásek, Pavel Klavík +2
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). Co…