Abstract
Computing a crossing minimum drawing of a given planar graph G augmented by an additional edge e where all crossings involve e, has been a long standing open problem in graph drawing. Alternatively, the problem can be stated as finding a combinatorial embedding of a planar graph G where the given edge e can be inserted with the minimum number of crossings. Many problems concerned with the optimization over the set of all combinatorial embeddings of a planar graph turned out to be NP-hard. Surprisingly, we found a conceptually simple linear time algorithm based on SPQR-trees, that is able to find a solution with the minimum number of crossings.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
Author information
Authors and Affiliations
Corresponding authors
Rights and permissions
About this article
Cite this article
Gutwenger, C., Mutzel, P. & Weiskircher, R. Inserting an Edge into a Planar Graph. Algorithmica 41, 289–308 (2005). https://doi.org/10.1007/s00453-004-1128-8
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00453-004-1128-8