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-01-01
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.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.
