@techreport{ee42aede67fe4780a2c747ef7e5ac1b5,

title = "Extending simple drawings with one edge is hard",

abstract = " A simple drawing $D(G)$ of a graph $G = (V,E)$ is a drawing in which two edges have at most one point in common that is either an endpoint or a proper crossing. An edge $e$ from the complement of $ G $ can be inserted into $D(G)$ if there exists a simple drawing of $G' = (V, E\cup \{e\})$ containing $D(G)$ as a subdrawing. We show that it is NP-complete to decide whether a given edge can be inserted into a simple drawing, by this solving an open question by Arroyo, Derka, and Parada. ",

keywords = "cs.CG",

author = "Alan Arroyo and Fabian Klute and Irene Parada and Raimund Seidel and Birgit Vogtenhuber and Tilo Wiedera",

note = "10 pages",

year = "2019",

month = sep,

day = "16",

language = "undefiniert/unbekannt",

series = "arXiv.org e-Print archive",

publisher = "Cornell University Library",

type = "WorkingPaper",

institution = "Cornell University Library",

}