3 papers
cs.DS2026
Parameterized Complexity of Power Network Design: Coordinating Cable Placement is Hard
Thekla Hamm, Bart M. P. Jansen, Faezeh Motiei
We study generalizations of the Steiner Tree problem motivated by the design of power networks. While Steiner Tree asks for a single minimum-cost tree connecting given terminal ver…
cs.DS2025
A Dichotomy for 1-Planarity with Restricted Crossing Types Parameterized by Treewidth
Sergio Cabello, Alexander Dobler, Gašper Fijavž +2
A drawing of a graph is 1-planar if each edge participates in at most one crossing and adjacent edges do not cross. Up to symmetry, each crossing in a 1-planar drawing belongs to o…
cs.CG2024
Computing crossing numbers with topological and geometric restrictions
Thekla Hamm, Fabian Klute, Irene Parada
Computing the crossing number of a graph is one of the most classical problems in computational geometry. Both it and numerous variations of the problem have been studied, and over…