Eiben, Eduard ;
Ganian, Robert ;
Hamm, Thekla ;
Klute, Fabian ;
Nöllenburg, Martin
Extending Partial 1Planar Drawings
Abstract
Algorithmic extension problems of partial graph representations such as planar graph drawings or geometric intersection representations are of growing interest in topological graph theory and graph drawing. In such an extension problem, we are given a tuple (G,H,ℋ) consisting of a graph G, a connected subgraph H of G and a drawing ℋ of H, and the task is to extend ℋ into a drawing of G while maintaining some desired property of the drawing, such as planarity.
In this paper we study the problem of extending partial 1planar drawings, which are drawings in the plane that allow each edge to have at most one crossing. In addition we consider the subclass of ICplanar drawings, which are 1planar drawings with independent crossings. Recognizing 1planar graphs as well as ICplanar graphs is NPcomplete and the NPcompleteness easily carries over to the extension problem. Therefore, our focus lies on establishing the tractability of such extension problems in a weaker sense than polynomialtime tractability. Here, we show that both problems are fixedparameter tractable when parameterized by the number of edges missing from H, i.e., the edge deletion distance between H and G. The second part of the paper then turns to a more powerful parameterization which is based on measuring the vertex+edge deletion distance between the partial and complete drawing, i.e., the minimum number of vertices and edges that need to be deleted to obtain H from G.
BibTeX  Entry
@InProceedings{eiben_et_al:LIPIcs:2020:12450,
author = {Eduard Eiben and Robert Ganian and Thekla Hamm and Fabian Klute and Martin N{\"o}llenburg},
title = {{Extending Partial 1Planar Drawings}},
booktitle = {47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)},
pages = {43:143:19},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771382},
ISSN = {18688969},
year = {2020},
volume = {168},
editor = {Artur Czumaj and Anuj Dawar and Emanuela Merelli},
publisher = {Schloss DagstuhlLeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/12450},
URN = {urn:nbn:de:0030drops124509},
doi = {10.4230/LIPIcs.ICALP.2020.43},
annote = {Keywords: Extension problems, 1planarity, parameterized algorithms}
}
29.06.2020
Keywords: 

Extension problems, 1planarity, parameterized algorithms 
Seminar: 

47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)

Issue date: 

2020 
Date of publication: 

29.06.2020 