3 papers
math.CO2026
Two Results on Outer-String Graphs
Todor AntiÄ, VÃt JelÃnek, Jan KratochvÃl +1
An \emph{outer-string representation} of a graph is an intersection representation of where vertices are represented by curves (strings) inside the unit disk and each curve…
cs.CG2026
Grounded String Representations of Series-Parallel Graphs without Transitive Edges
Sabine Cornelsen, Jan KratochvÃl, Miriam Münch +3
In a {\em grounded string representation} of a graph there is a horizontal line and each vertex is represented as a simple curve below with one end point on su…
cs.DM2025
Hamiltonian path and Hamiltonian cycle are solvable in polynomial time in graphs of bounded independence number
Nikola JedliÄková, Jan KratochvÃl
A Hamiltonian path (a Hamiltonian cycle) in a graph is a path (a cycle, respectively) that traverses all of its vertices. The problems of deciding their existence in an input graph…