Record link: 
http://hdl.handle.net/20.500.12708/225288
-
Title: 
Partial Level Planarity Parameterized by the Size of the Missing Graph
en
Citation: 
Depian, T., Fink, S. D., Klemz, B., Ganian, R., Nöllenburg, M., & Sieper, M. D. (2025). Partial Level Planarity Parameterized by the Size of the Missing Graph. In EUROCG’25 Booklet of Abstracts. EuroCG 2025, Liblice, Czechia. http://hdl.handle.net/20.500.12708/225288
-
Publication Type: 
Inproceedings - Abstract Book Contribution
en
Language: 
English
-
Authors: 
Depian, Thomas 
Fink, Simon D. 
Klemz, Boris 
Ganian, Robert 
Nöllenburg, Martin 
Sieper, Marie Diana 
-
Organisational Unit: 
E192-01 - Forschungsbereich Algorithms and Complexity 
E056-13 - Fachbereich LogiCS 
-
Published in: 
EUROCG’25 Booklet of Abstracts 
-
Date (published): 
11-Apr-2025
-
Event name: 
EuroCG 2025 
en
Event date: 
9-Apr-2025 - 11-Apr-2025
-
Event place: 
Liblice, Czechia
-
Number of Pages: 
10
-
Peer reviewed: 
Yes
-
Keywords: 
partial level planarity; parameterized complexity; drawing extension
en
Abstract: 
A level planar drawing of a graph G is crossing-free, has y-monotone edges, and uses levels specified in the input as y-coordinates of vertices. In Partial Level Planarity (PLP), we are given a level planar drawing of a subgraph H of G and are asked to extend it to a drawing of G. Results by Brückner and Rutter [SODA 2017] and Klemz and Rote [ACM Trans. Alg. 2019] show that PLP remains NP-complete even for severely restricted instances, which makes it resistant against parameterized tractability for most well-known parameters. In this paper, we use the size of the missing graph, i.e., of G \ H, as a parameter to identify fixed-parameter tractable fragments of PLP.
en
Research Areas: 
Logic and Computation: 100%
-
Science Branch: 
1020 - Informatik: 80%
1010 - Mathematik: 20%
-
Appears in Collections:
Conference Paper

Show full item record

Page view(s)

60
checked on Jan 22, 2026

Google ScholarTM

Check