Maximum Upward Planar Subgraphs of Embedded Planar Digraphs

Binucci, Carla and Didimo, Walter and Giordano, Francesco (2008) Maximum Upward Planar Subgraphs of Embedded Planar Digraphs. In: Graph Drawing 15th International Symposium, GD 2007, September 24-26, 2007 , pp. 195-206(Official URL: http://dx.doi.org/10.1007/978-3-540-77537-9_20).

Full text not available from this repository.

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.

Item Type: Conference Paper
Additional Information: 10.1007/978-3-540-77537-9_20
Classifications: P Styles > P.840 Upward
URI: http://gdea.informatik.uni-koeln.de/id/eprint/838

Actions (login required)

View Item View Item