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

    Abstract

    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
    Pages195-198
    Publication statusPublished - 2005

    Fingerprint

    Topological Graph
    Geometric Graphs
    Spanning tree
    Integer Program
    Linear Program
    Connected graph
    NP-complete problem
    Formulation
    Computing
    Approximation

    Cite this

    Knauer, C., Schramm, É., Spillner, A., & Wolff, A. (2005). Spanning trees with few crossings in geometric and topological graphs. In M. T. Berg, de (Ed.), Abstracts 21th European Workshop on Computational Geometry (EWCG 2005, Eindhoven, The Netherlands, March 9-11, 2005) (pp. 195-198). Technische Universiteit Eindhoven.
    Knauer, C. ; Schramm, É. ; Spillner, A. ; Wolff, A. / Spanning trees with few crossings in geometric and topological graphs. Abstracts 21th European Workshop on Computational Geometry (EWCG 2005, Eindhoven, The Netherlands, March 9-11, 2005). editor / M.T. Berg, de. Technische Universiteit Eindhoven, 2005. pp. 195-198
    @inproceedings{4737086555b44830878f73adc333e689,
    title = "Spanning trees with few crossings in geometric and topological graphs",
    abstract = "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.",
    author = "C. Knauer and {\'E}. Schramm and A. Spillner and A. Wolff",
    year = "2005",
    language = "English",
    pages = "195--198",
    editor = "{Berg, de}, M.T.",
    booktitle = "Abstracts 21th European Workshop on Computational Geometry (EWCG 2005, Eindhoven, The Netherlands, March 9-11, 2005)",
    publisher = "Technische Universiteit Eindhoven",

    }

    Knauer, C, Schramm, É, Spillner, A & Wolff, A 2005, Spanning trees with few crossings in geometric and topological graphs. in MT Berg, de (ed.), Abstracts 21th European Workshop on Computational Geometry (EWCG 2005, Eindhoven, The Netherlands, March 9-11, 2005). Technische Universiteit Eindhoven, pp. 195-198.

    Spanning trees with few crossings in geometric and topological graphs. / Knauer, C.; Schramm, É.; Spillner, A.; Wolff, A.

    Abstracts 21th European Workshop on Computational Geometry (EWCG 2005, Eindhoven, The Netherlands, March 9-11, 2005). ed. / M.T. Berg, de. Technische Universiteit Eindhoven, 2005. p. 195-198.

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

    TY - GEN

    T1 - Spanning trees with few crossings in geometric and topological graphs

    AU - Knauer, C.

    AU - Schramm, É.

    AU - Spillner, A.

    AU - Wolff, A.

    PY - 2005

    Y1 - 2005

    N2 - 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.

    AB - 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.

    M3 - Conference contribution

    SP - 195

    EP - 198

    BT - Abstracts 21th European Workshop on Computational Geometry (EWCG 2005, Eindhoven, The Netherlands, March 9-11, 2005)

    A2 - Berg, de, M.T.

    PB - Technische Universiteit Eindhoven

    ER -

    Knauer C, Schramm É, Spillner A, Wolff A. Spanning trees with few crossings in geometric and topological graphs. In Berg, de MT, editor, Abstracts 21th European Workshop on Computational Geometry (EWCG 2005, Eindhoven, The Netherlands, March 9-11, 2005). Technische Universiteit Eindhoven. 2005. p. 195-198