**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*, to appear.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.

(Slides)

Co-authors – Publications – David Eppstein – Theory Group – Inf. & Comp. Sci. – UC Irvine

Semi-automatically filtered from a common source file.