We study the NodeTrix planarity testing problem for flat clustered graphs when the maximum size of each cluster is bounded by a constant k. We consider both the case when the sides of the matrices to which the edges are incident are fixed and the case when they can be arbitrarily chosen. We show that NodeTrix planarity testing with fixed sides can be solved in O(k3k+3/2n3) time for every flat clustered graph that can be reduced to a partial 2-tree by collapsing its clusters into single vertices. In the general case, NodeTrix planarity testing with fixed sides can be solved in O(n3) time for k = 2, but it is NP-complete for any k ≥ 3. NodeTrix planarity testing remains NP-complete also in the free side model when k > 4.

Di Giacomo, E., Liotta, G., Patrignani, M., & Tappini, A. (2018). NodeTrix planarity testing with small clusters. In Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) (pp.479-491). Springer Verlag [10.1007/978-3-319-73915-1_37].

NodeTrix planarity testing with small clusters

DI GIACOMO, EMILIO;LIOTTA, GIUSEPPE;Patrignani, Maurizio;
2018

Abstract

We study the NodeTrix planarity testing problem for flat clustered graphs when the maximum size of each cluster is bounded by a constant k. We consider both the case when the sides of the matrices to which the edges are incident are fixed and the case when they can be arbitrarily chosen. We show that NodeTrix planarity testing with fixed sides can be solved in O(k3k+3/2n3) time for every flat clustered graph that can be reduced to a partial 2-tree by collapsing its clusters into single vertices. In the general case, NodeTrix planarity testing with fixed sides can be solved in O(n3) time for k = 2, but it is NP-complete for any k ≥ 3. NodeTrix planarity testing remains NP-complete also in the free side model when k > 4.
9783319739144
Di Giacomo, E., Liotta, G., Patrignani, M., & Tappini, A. (2018). NodeTrix planarity testing with small clusters. In Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) (pp.479-491). Springer Verlag [10.1007/978-3-319-73915-1_37].
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: http://hdl.handle.net/11590/329882
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 7
  • ???jsp.display-item.citation.isi??? ND
social impact