### Abstract

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 |

### Fingerprint

### Cite this

*Abstracts 21th European Workshop on Computational Geometry (EWCG 2005, Eindhoven, The Netherlands, March 9-11, 2005)*(pp. 195-198). Technische Universiteit Eindhoven.

}

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

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 -