Configurations with few crossings in topological graphs
Copyright policy )Configurations with few crossings in topological graphs
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.
- Freie Universität Berlin Germany
- Karlsruhe Institute of Technology Germany
- Friedrich Schiller University Jena Germany
- Universität Karlsruhe
- Technical University Eindhoven Netherlands
ddc:004, fixed-parameter algorithms, Monte-Carlo algorithms, Control and Optimization, DATA processing & computer science, Crossing minimization, crossing minimization, Fixed-parameter algorithms, Approximation algorithms, 004, Planar graphs; geometric and topological aspects of graph theory, Computer Science Applications, Topological graphs, Computational Mathematics, Computational Theory and Mathematics, Graph algorithms (graph-theoretic aspects), Graph theory (including graph drawing) in computer science, Geometry and Topology, Non-approximability, approximation algorithms, info:eu-repo/classification/ddc/004
ddc:004, fixed-parameter algorithms, Monte-Carlo algorithms, Control and Optimization, DATA processing & computer science, Crossing minimization, crossing minimization, Fixed-parameter algorithms, Approximation algorithms, 004, Planar graphs; geometric and topological aspects of graph theory, Computer Science Applications, Topological graphs, Computational Mathematics, Computational Theory and Mathematics, Graph algorithms (graph-theoretic aspects), Graph theory (including graph drawing) in computer science, Geometry and Topology, Non-approximability, approximation algorithms, info:eu-repo/classification/ddc/004
selected citations These citations are derived from selected sources.This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).7 popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.Average influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).Average impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.Average
Citations provided by BIP!Popularity provided by BIP!