Computing Crossing Numbers in Quadratic Time
<|reference_start|>Computing Crossing Numbers in Quadratic Time: We 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.<|reference_end|>
@article{grohe2000computing,
    title={Computing Crossing Numbers in Quadratic Time},
    author={Martin Grohe},
    journal={arXiv preprint arXiv:cs/0009010},
    year={2000},
    archivePrefix={arXiv},
    eprint={cs/0009010},
    primaryClass={cs.DS cs.DM}
}