35 citations · 53 across the 6 of their papers we have counts for
3 papers · 1 filter
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…