Inserting one edge into a simple drawing is hard

Alan Arroyo, Fabian Klute, Irene Parada, Raimund Seidel, Birgit Vogtenhuber*, Tilo Wiedera

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference paperpeer-review


A simple drawing D(G) of a graph G is one where each pair of edges share at most one point: either a common endpoint or a proper crossing. An edge e in the complement of G can be inserted into D(G) if there exists a simple drawing of G+ e extending D(G). As a result of Levi’s Enlargement Lemma, if a drawing is rectilinear (pseudolinear), that is, the edges can be extended into an arrangement of lines (pseudolines), then any edge in the complement of G can be inserted. In contrast, we show that it is NP-complete to decide whether one edge can be inserted into a simple drawing. This remains true even if we assume that the drawing is pseudocircular, that is, the edges can be extended to an arrangement of pseudocircles. On the positive side, we show that, given an arrangement of pseudocircles A and a pseudosegment σ, it can be decided in polynomial time whether there exists a pseudocircle Φ σ extending σ for which A∪ { Φ σ} is again an arrangement of pseudocircles.

Original languageEnglish
Title of host publicationGraph-Theoretic Concepts in Computer Science - 46th International Workshop, WG 2020, Revised Selected Papers
EditorsIsolde Adler, Haiko Müller
Place of PublicationLeeds, United Kingdom
Number of pages14
Publication statusPublished - 1 Jan 2020
Event46th International Workshop on Graph-Theoretic Concepts in Computer Science: WG 2020 - Virtuell, Leeds, United Kingdom
Duration: 24 Jun 202026 Jun 2020

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume12301 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference46th International Workshop on Graph-Theoretic Concepts in Computer Science
Country/TerritoryUnited Kingdom
CityVirtuell, Leeds

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Cite this