[Back]

E. Eiben, R. Ganian, T. Hamm, F. Klute, M. Nöllenburg:
"Extending Partial 1-Planar Drawings";
Talk: International Colloquium on Automata, Languages and Programming (ICALP), Saarbrücken, Germany; 2020-07-08 - 2020-07-11; in: "47th International Colloquium on Automata, Languages, and Programming", Leibniz International Proceedings in Informatics, 168 (2020), ISBN: 978-3-95977-138-2; 1 - 19.

Algorithmic extension problems of partial graph representations such as planar graph drawings orgeometric intersection representations are of growing interest in topological graph theory and graphdrawing. In such an extension problem, we are given a tuple(G, H,H)consisting of a graphG, aconnected subgraphHofGand a drawingHofH, and the task is to extendHinto a drawing ofGwhile maintaining some desired property of the drawing, such as planarity.In this paper we study the problem of extending partial 1-planar drawings, which are drawings inthe plane that allow each edge to have at most one crossing. In addition we consider the subclass ofIC-planar drawings, which are 1-planar drawings with independent crossings. Recognizing 1-planargraphs as well as IC-planar graphs isNP-complete and theNP-completeness easily carries over tothe extension problem. Therefore, our focus lies on establishing the tractability of such extensionproblems in a weaker sense than polynomial-time tractability. Here, we show that both problems arefixed-parameter tractable when parameterized by the number of edges missing fromH, i.e., the edgedeletion distance betweenHandG. The second part of the paper then turns to a more powerfulparameterization which is based on measuring the vertex+edge deletion distance between the partialand complete drawing, i.e., the minimum number of vertices and edges that need to be deleted toobtainHfromG.

http://dx.doi.org/10.4230/LIPIcs.ICALP.2020.0

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