Computing Crossing Numbers in Quadratic Time

Simple item page
dc.creatorGrohe, Martin
dc.date2000-09-18
dc.date2000-10-10
dc.date.accessioned2026-07-07T03:16:33Z
dc.date.available2026-07-07T03:16:33Z
dc.descriptionWe show that for every fixed non-negative integer k there is a quadratic time algorithm that decides whether a given graph has crossing number at most k and, if this is the case, computes a drawing of the graph in the plane with at most k crossings.
dc.identifierhttps://arxiv.org/abs/cs/0009010
dc.identifierhttp://arxiv.org/abs/cs/0009010
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/30392
dc.subjectData Structures and Algorithms
dc.subjectDiscrete Mathematics
dc.subjectF.2.2;G.2.2
dc.titleComputing Crossing Numbers in Quadratic Time
dc.typetext

Files

Collections

arXiv