3 papers
cs.DS2026
Finding Minimum Distance Preservers: A Parameterized Study
Kirill Simonov, Farehe Soheil, Shaily Verma
For a given graph and a subset of vertices , a \emph{distance preserver} is a subgraph of that preserves shortest paths between the vertices of . We distinguish betwe…
cs.DS2023
The -Planar Edge Completion Problem is Fixed-Parameter Tractable
Liana Khazaliya, Philipp Kindermann, Giuseppe Liotta +2
The problem of deciding whether a biconnected planar digraph can be augmented to become an -planar graph by adding a set of oriented edges i…
cs.CG2023
Upward and Orthogonal Planarity are W[1]-hard Parameterized by Treewidth
Bart M. P. Jansen, Liana Khazaliya, Philipp Kindermann +3
Upward planarity testing and Rectilinear planarity testing are central problems in graph drawing. It is known that they are both NP-complete, but XP when parameterized by treewidth…