Name
Abstract | ||
|---|---|---|
We present several polynomial-time algorithms for c-planarity testing for cluster hierarchyC containing clusters of size at most three. The main result is an O(jCj3 + n)-time algorithm for clusters of size at most three on a cycle. The result is then generalized to a special class of Eulerian graphs, namely graphs obtained from a 3-connected planar graph of xed size k by multiplying and then subdividing edges. An O(3k k n3)-time algorithm is presented. We further give an O(jCj2 +n)-time algorithm for general 3-connected planar graphs. |
Year | Venue | Keywords |
|---|---|---|
2009 | J. Graph Algorithms Appl. | eulerian graph,planar graph |
Field | DocType | Volume |
Discrete mathematics,Outerplanar graph,Combinatorics,Line graph,Cycle basis,Polyhedral graph,Book embedding,1-planar graph,Planar graph,Pancyclic graph,Mathematics | Journal | 13 |
Issue | Citations | PageRank |
3 | 12 | 0.57 |
References | Authors | |
12 | 6 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Eva Jelínková | 1 | 51 | 5.58 |
| jan kara | 2 | 12 | 0.57 |
| Jan Kratochvíl | 3 | 1751 | 151.84 |
| Martin Pergel | 4 | 72 | 6.38 |
| ondrej suchy | 5 | 12 | 0.57 |
| tomas vyskocil | 6 | 56 | 5.61 |