Name
Abstract | ||
|---|---|---|
We consider the problem of testing a digraph G = (V,E) for upward planarity. In particular we present two fixed-parameter tractable algorithms for testing the upward planarity of G. Let n = |V|, let t be the number of triconnected components of G, and let c be the number of cut-vertices of G. The first upward planarity testing algorithm we present runs in O(2t · t! · n2)–time. The previously known best result is an O(t! · 8t · n3 + 23·2c · t3·2c · t! · 8t · n)-time algorithm by Chan. We use the kernelisation technique to develop a second upward planarity testing algorithm which runs in O(n2 + k4(2k + 1)!) time, where k = |E| – |V|. We also define a class of non upward planar digraphs. |
Year | DOI | Venue |
|---|---|---|
2005 | 10.1007/978-3-540-30577-4_23 | Int. J. Found. Comput. Sci. |
Keywords | Field | DocType |
kernelisation technique,fixed-parameter tractable algorithm,non upward planar digraph,present run,best result,upward planarity,time algorithm,triconnected component,digraph g,upward planarity testing algorithm | Discrete mathematics,Combinatorics,Planarity testing,Algorithm,Planar,SPQR tree,Digraph,Mathematics | Conference |
Volume | Issue | ISSN |
17 | 5 | 0302-9743 |
ISBN | Citations | PageRank |
3-540-24302-X | 15 | 0.76 |
References | Authors | |
14 | 2 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Patrick Healy | 1 | 21 | 2.63 |
| Karol Lynch | 2 | 25 | 2.20 |