E. Eiben, R. Ganian, T. Hamm,F. Klute, M. Nöllenburg:

"Extending Nearly Complete 1-Planar Drawings in Polynomial Time";

Talk: International Symposium on Mathematical Foundations of Computer Science (MFCS), Prag, Tschechien; 2020-08-24 - 2020-08-28; in: "45th International Symposium on Mathematical Foundations of Computer Science", LIPIcs, 170 (2020), ISBN: 978-3-95977-159-7; 1 - 16.

The problem of extending partial geometric graph representations such as plane graphs has received

considerable attention in recent years. In particular, given a graph G, a connected subgraph H of G

and a drawing H of H, the extension problem asks whether H can be extended into a drawing of G

while maintaining some desired property of the drawing (e.g., planarity).

In their breakthrough result, Angelini et al. [ACM TALG 2015] showed that the extension

problem is polynomial-time solvable when the aim is to preserve planarity. Very recently we

considered this problem for partial 1-planar drawings [ICALP 2020], which are drawings in the plane

that allow each edge to have at most one crossing. The most important question identified and left

open in that work is whether the problem can be solved in polynomial time when H can be obtained

from G by deleting a bounded number of vertices and edges. In this work, we answer this question

positively by providing a constructive polynomial-time decision algorithm.

http://dx.doi.org/10.4230/LIPIcs.MFCS.2020.31

https://publik.tuwien.ac.at/files/publik_292473.pdf

Created from the Publication Database of the Vienna University of Technology.