TY - GEN
T1 - Crossing-optimal extension of simple drawings
AU - Ganian, Robert
AU - Hamm, Thekla
AU - Klute, Fabian
AU - Parada, Irene
AU - Vogtenhuber, Birgit
N1 - Funding Information:
Funding Robert Ganian: Supported by the Austrian Science Fund (FWF) via projects Y1329 (Parameterized Analysis in Artificial Intelligence) and P31336 (New Frontiers for Parameterized Complexity). Thekla Hamm: Supported by the Austrian Science Fund (FWF) via projects Y1329 (Parameterized Analysis in Artificial Intelligence), P31336 (New Frontiers for Parameterized Complexity) and W1255-N23. Fabian Klute: Supported by the Netherlands Organisation for Scientific Research (NWO) under project no. 612.001.651. Birgit Vogtenhuber: Partially supported by Austrian Science Fund (FWF) within the collaborative DACH project Arrangements and Drawings as FWF project I 3340-N35.
Publisher Copyright:
© 2021 Robert Ganian, Thekla Hamm, Fabian Klute, Irene Parada, and Birgit Vogtenhuber.
PY - 2021/7/1
Y1 - 2021/7/1
N2 - 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.
AB - 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.
KW - Crossing minimization
KW - Extension problems
KW - FPT-algorithms
KW - Simple drawings
UR - http://www.scopus.com/inward/record.url?scp=85115321625&partnerID=8YFLogxK
U2 - 10.4230/LIPIcs.ICALP.2021.72
DO - 10.4230/LIPIcs.ICALP.2021.72
M3 - Conference paper
AN - SCOPUS:85115321625
T3 - Leibniz International Proceedings in Informatics, LIPIcs
BT - 48th International Colloquium on Automata, Languages, and Programming, ICALP 2021
A2 - Bansal, Nikhil
A2 - Merelli, Emanuela
A2 - Worrell, James
PB - Schloss Dagstuhl - Leibniz-Zentrum für Informatik
T2 - 48th International Colloquium on Automata, Languages, and Programming, ICALP 2021
Y2 - 12 July 2021 through 16 July 2021
ER -