Publications with Philipp Kindermann
On the planar split thickness of graphs.
D. Eppstein, P. Kindermann, S. G. Kobourov, G. Liotta, A. Lubiw, A. Maignan, D. Mondal, H. Vosoughpour, S. Whitesides, and S. Wismath.
arXiv:1512.04839.
Proc. 12th Latin American Theoretical Informatics Symposium (LATIN 2016), Ensenada, Mexico.
Springer, Lecture Notes in Comp. Sci. 9644 (2016), pp. 403–415.
Algorithmica 80 (3): 977–994 (special issue for LATIN), 2018.We study the problem of splitting the vertices of a given graph into a bounded number of sub-vertices (with each edge attaching to one of the sub-vertices) in order to make the resulting graph planar. It is NP-complete, but can be approximated to within a constant factor, and is fixed-parameter tractable in the treewidth.