Crossing-optimal extension of simple drawings

Robert Ganian, Thekla Hamm, Fabian Klute, Irene Parada, Birgit Vogtenhuber

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


In extension problems of partial graph drawings one is given an incomplete drawing of an input graph G and is asked to complete the drawing while maintaining certain properties. A prominent area where such problems arise is that of crossing minimization. For plane drawings and various relaxations of these, there is a number of tractability as well as lower-bound results exploring the computational complexity of crossing-sensitive drawing extension problems. In contrast, comparatively few results are known on extension problems for the fundamental and broad class of simple drawings, that is, drawings in which each pair of edges intersects in at most one point. In fact, the extension problem of simple drawings has only recently been shown to be NP-hard even for inserting a single edge. In this paper we present tractability results for the crossing-sensitive extension problem of simple drawings. In particular, we show that the problem of inserting edges into a simple drawing is fixed-parameter tractable when parameterized by the number of edges to insert and an upper bound on newly created crossings. Using the same proof techniques, we are also able to answer several closely related variants of this problem, among others the extension problem for k-plane drawings. Moreover, using a different approach, we provide a single-exponential fixed-parameter algorithm for the case in which we are only trying to insert a single edge into the drawing.

Original languageEnglish
Title of host publication48th International Colloquium on Automata, Languages, and Programming, ICALP 2021
EditorsNikhil Bansal, Emanuela Merelli, James Worrell
PublisherSchloss Dagstuhl - Leibniz-Zentrum für Informatik
ISBN (Electronic)9783959771955
Publication statusPublished - 1 Jul 2021
Event48th International Colloquium on Automata, Languages, and Programming, ICALP 2021 - Virtual, Glasgow, United Kingdom
Duration: 12 Jul 202116 Jul 2021

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
ISSN (Print)1868-8969


Conference48th International Colloquium on Automata, Languages, and Programming, ICALP 2021
Country/TerritoryUnited Kingdom
CityVirtual, Glasgow


  • Crossing minimization
  • Extension problems
  • FPT-algorithms
  • Simple drawings

ASJC Scopus subject areas

  • Software


Dive into the research topics of 'Crossing-optimal extension of simple drawings'. Together they form a unique fingerprint.

Cite this