We study the complexity of testing whether a biconnected graph G = (V, E) is planar with the constraint that some cyclic orders of the edges incident to its vertices are allowed while some others are forbidden. The allowed cyclic orders are described by associating every vertex v of G with a set D(v) of FPQ-trees. Let tw be the treewidth of G and let Dmax be the maximum number of FPQ-trees per vertex. We show that the problem is FPT when parameterized by tw + Dmax, paraNP-hard when parameterized by Dmax, and W[1]-hard when parameterized by tw. We also consider NodeTrix planar representations of clustered graphs, where clusters are adjacency matrices and inter-cluster edges are non-intersecting simple curves. We prove that NodeTrix planarity with fixed sides is FPT when parameterized by the size of clusters plus the treewidth of the graph obtained by collapsing clusters to single vertices, provided that this graph is biconnected.(c) 2023 Elsevier Inc. All rights reserved.

Parameterized complexity of graph planarity with restricted cyclic orders

Liotta G.
;
Tappini A.
2023

Abstract

We study the complexity of testing whether a biconnected graph G = (V, E) is planar with the constraint that some cyclic orders of the edges incident to its vertices are allowed while some others are forbidden. The allowed cyclic orders are described by associating every vertex v of G with a set D(v) of FPQ-trees. Let tw be the treewidth of G and let Dmax be the maximum number of FPQ-trees per vertex. We show that the problem is FPT when parameterized by tw + Dmax, paraNP-hard when parameterized by Dmax, and W[1]-hard when parameterized by tw. We also consider NodeTrix planar representations of clustered graphs, where clusters are adjacency matrices and inter-cluster edges are non-intersecting simple curves. We prove that NodeTrix planarity with fixed sides is FPT when parameterized by the size of clusters plus the treewidth of the graph obtained by collapsing clusters to single vertices, provided that this graph is biconnected.(c) 2023 Elsevier Inc. All rights reserved.
2023
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11391/1566915
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 2
  • ???jsp.display-item.citation.isi??? 1
social impact