KIT | KIT-Bibliothek | Impressum | Datenschutz
Open Access Logo
URN: urn:nbn:de:swb:90-41224

Configuations with few crossings in topological graphs

Knauer, Christian; Schramme, Etienne; Spillner, Andreas; Wolff, Alexander


In this paper we study the problem of computing
subgraphs of a certain configuration in a given
topological graph G such that the number of
crossings in the subgraph is minimum. The
configurations that we consider are spanning
trees, s-t paths, cycles, matchings, and
kappa-factors for kappa in {1,2}. We show that it
is NP-hard to approximate the minimum number of
crossings for these configurations within a factor
of k^(1-epsilon) for any epsilon > 0, where k is
the number of crossings in G. We then show that
the problems are fixed-parameter tractable if we
use the number of crossings in the given graph as
the parameter. Finally we present a mixed-integer
linear program formulation for each problem and a
simple but effective heuristic for spanning trees.

Zugehörige Institution(en) am KIT Institut für Theoretische Informatik (ITI)
Publikationstyp Forschungsbericht
Jahr 2005
Sprache Englisch
Identifikator ISSN: 1432-7864

KITopen-ID: 1000004122
Verlag Karlsruhe
Serie Interner Bericht. Fakultät für Informatik, Universität Karlsruhe ; 2005,24
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft KITopen Landing Page