The C-Planarity problem asks for a drawing of a clustered graph, i.e., a graph whose vertices belong to properly nested clusters, in which each cluster is represented by a simple closed region with no edge-edge crossings, no region-region crossings, and no unnecessary edge-region crossings. We study C-Planarity for embedded flat clustered graphs, graphs with a fixed combinatorial embedding whose clusters partition the vertex set. Our main result is a subexponential-time algorithm to test C-Planarity for these graphs when their face size is bounded. Furthermore, we consider a variation of the notion of embedded tree decomposition in which, for each face, including the outer face, there is a bag that contains every vertex of the face. We show that C-Planarity is fixed-parameter tractable with the embedded-width of the underlying graph and the number of disconnected clusters as parameters.

Da Lozzo, G., Eppstein, D., Goodrich, M.T., Gupta, S. (2018). Subexponential-time and FPT algorithms for embedded flat clustered planarity. In Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) (pp.111-124). Springer Verlag [10.1007/978-3-030-00256-5_10].

Subexponential-time and FPT algorithms for embedded flat clustered planarity

Da Lozzo, Giordano;
2018-01-01

Abstract

The C-Planarity problem asks for a drawing of a clustered graph, i.e., a graph whose vertices belong to properly nested clusters, in which each cluster is represented by a simple closed region with no edge-edge crossings, no region-region crossings, and no unnecessary edge-region crossings. We study C-Planarity for embedded flat clustered graphs, graphs with a fixed combinatorial embedding whose clusters partition the vertex set. Our main result is a subexponential-time algorithm to test C-Planarity for these graphs when their face size is bounded. Furthermore, we consider a variation of the notion of embedded tree decomposition in which, for each face, including the outer face, there is a bag that contains every vertex of the face. We show that C-Planarity is fixed-parameter tractable with the embedded-width of the underlying graph and the number of disconnected clusters as parameters.
2018
9783030002558
Da Lozzo, G., Eppstein, D., Goodrich, M.T., Gupta, S. (2018). Subexponential-time and FPT algorithms for embedded flat clustered planarity. In Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) (pp.111-124). Springer Verlag [10.1007/978-3-030-00256-5_10].
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/11590/345350
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 9
  • ???jsp.display-item.citation.isi??? ND
social impact