35 citations · 100 across the 23 of their papers we have counts for
8 papers · 1 filter
A note on planar partial 3-trees
Jan Kratochvíl, Michal Vaner
It implicitly follows from the work of [Colbourn, El-Mallah: On two dual classes of planar graphs. Discrete Mathematics 80(1): 21-40 (1990)] that every planar partial 3-tree is a s…
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…
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…
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…
A Kuratowski-Type Theorem for Planarity of Partially Embedded Graphs
Vít Jelínek, Jan Kratochvíl, Ignaz Rutter
A partially embedded graph (or PEG) is a triple (G,H,\H), where G is a graph, H is a subgraph of G, and \H is a planar embedding of H. We say that a PEG (G,H,\H) is planar if the g…