Spanning trees with few crossings in geometric and topological graphs

C. Knauer, É. Schramm, A. Spillner, A. Wolff

    Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademic


    We study the problem of computing a spanning tree in a connected topological graph such that the number of crossings in the spanning tree is minimum. We show it is NP-hard to find a good approximation of the minimum number of crossings even in geometric graphs. On the other hand we show that the problem is fixed-parameter tractable and present a mixed integer linear program formulation.
    Original languageEnglish
    Title of host publicationAbstracts 21th European Workshop on Computational Geometry (EWCG 2005, Eindhoven, The Netherlands, March 9-11, 2005)
    EditorsM.T. Berg, de
    PublisherTechnische Universiteit Eindhoven
    Publication statusPublished - 2005


    Dive into the research topics of 'Spanning trees with few crossings in geometric and topological graphs'. Together they form a unique fingerprint.

    Cite this