This paper presents an extensive study on the problem of computing maximum upward planar subgraphs of embedded planar digraphs: Complexity results, algorithms, and experiments are presented. Namely: (i) We prove that the addressed problem is NP-Hard; (ii) A fast heuristic and an exponential-time exact algorithm are described; (iii) A wide experimental analysis is performed to show the effectiveness of our techniques.

Maximum Upward Planar Subgraphs of Embedded Planar Digraphs

BINUCCI, Carla;DIDIMO, WALTER;GIORDANO, FRANCESCO
2008

Abstract

This paper presents an extensive study on the problem of computing maximum upward planar subgraphs of embedded planar digraphs: Complexity results, algorithms, and experiments are presented. Namely: (i) We prove that the addressed problem is NP-Hard; (ii) A fast heuristic and an exponential-time exact algorithm are described; (iii) A wide experimental analysis is performed to show the effectiveness of our techniques.
9783540775362
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/11391/31794
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 1
  • ???jsp.display-item.citation.isi??? ND
social impact