Spanning trees with few crossings in geometric and topological graphs

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

Spanning trees with few crossings in geometric and topological graphs

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

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic

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 language	English
Title of host publication	Abstracts 21th European Workshop on Computational Geometry (EWCG 2005, Eindhoven, The Netherlands, March 9-11, 2005)
Editors	M.T. Berg, de
Publisher	Technische Universiteit Eindhoven
Pages	195-198
Publication status	Published - 2005

Cite this

@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",

}

Spanning trees with few crossings in geometric and topological graphs. / Knauer, C.; Schramm, É.; Spillner, A. et al.
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 proceeding › Conference contribution › Academic

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 -

Spanning trees with few crossings in geometric and topological graphs

Abstract

Fingerprint

Cite this