Configurations with few crossings in topological graphs

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

Research output: Contribution to journalArticleAcademicpeer-review

6 Citations (Scopus)

Abstract

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 ¿-factors for ¿{1,2}. We show that it is NP-hard to approximate the minimum number of crossings for these configurations within a factor of k1-e for any e>0, where k is the number of crossings in G. We then give a simple fixed-parameter algorithm that tests in O(2k) time whether G has a crossing-free configuration for any of the above, where the O-notation neglects polynomial terms. For some configurations we have faster algorithms. The respective running times are O(1.9999992k) for spanning trees and for s-t paths and cycles. For spanning trees we also have an O(1.968k)-time Monte-Carlo algorithm. Each O(ßk)-time decision algorithm can be turned into an O((ß+1)k)-time optimization algorithm that computes a configuration with the minimum number of crossings.
Original languageEnglish
Pages (from-to)104-114
JournalComputational Geometry
Volume37
Issue number2
DOIs
Publication statusPublished - 2007

Fingerprint Dive into the research topics of 'Configurations with few crossings in topological graphs'. Together they form a unique fingerprint.

Cite this