35 citations · 53 across the 6 of their papers we have counts for
7 papers
Irreversible 2-conversion set in graphs of bounded degree
Jan Kynčl, Bernard Lidický, Tomáš Vyskočil
An irreversible -threshold process (also a -neighbor bootstrap percolation) is a dynamic process on a graph where vertices change color from white to black if they have at le…
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…
Bend-Bounded Path Intersection Graphs: Sausages, Noodles, and Waffles on a Grill
Steven Chaplick, Vít Jelínek, Jan Kratochvíl +1
In this paper we study properties of intersection graphs of k-bend paths in the rectangular grid. A k-bend path is a path with at most k 90 degree turns. The class of graphs repres…
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…
The Planar Slope Number of Planar Partial 3-Trees of Bounded Degree
Vít Jelínek, Eva Jelínková, Jan Kratochvíl +3
It is known that every planar graph has a planar embedding where edges are represented by non-crossing straight-line segments. We study the planar slope number, i.e., the minimum n…
Segment representation of a subclass of co-planar graphs
Mathew C. Francis, Jan Kratochvíl, Tomáš Vyskočil
A graph is said to be a segment graph if its vertices can be mapped to line segments in the plane such that two vertices have an edge between them if and only if their correspondin…