The upward planarity testing problem is known to be NP-hard. We describe an O(n^4)-time upward planarity testing and embedding algorithm for the class of digraphs that do not contain rigid triconnected components. We also present a new FPT algorithm that solves the upward planarity testing and embedding problem for general digraphs.
Upward Spirality and Upward Planarity Testing
DIDIMO, WALTER;GIORDANO, FRANCESCO;LIOTTA, Giuseppe
2006
Abstract
The upward planarity testing problem is known to be NP-hard. We describe an O(n^4)-time upward planarity testing and embedding algorithm for the class of digraphs that do not contain rigid triconnected components. We also present a new FPT algorithm that solves the upward planarity testing and embedding problem for general digraphs.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.
