Topological sweep of the complete graph Original Research Article

We present a novel, simple and easily implementable algorithm to report all intersections in an embedding of a complete graph. For graphs with image vertices and complexity image measured as the number of segments of the embedding, the running time of the algorithm is image, where image is the maximum number of edges cut by any vertical line. Our algorithm handles degeneracies, such as vertical edges or multiply intersecting edges, without requiring numerical perturbations to achieve general position.