Name
Abstract | ||
|---|---|---|
The skewness sk(G) of a graph G = (V, E) is the smallest integer sk(G) >= 0 such that a planar graph can be obtained from G by the removal of sk(C) edges. The splitting number sp(G) of C is the smallest integer sp(G) >= 0 such that a planar graph can be obtained from G by sp(G) vertex splitting operations. The vertex deletion vd(G) of G is the smallest integer vd(G) >= 0 such that a planar graph can be obtained from G by the removal of vd(G) vertices. Regular toroidal meshes are popular topologies for the connection networks of SIMD parallel machines. The best known of these meshes is the rectangular toroidal mesh C-m x C-n for which is known the skewness, the splitting number and the vertex deletion. In this work we consider two related families: a triangulation Tc-m x c(n) of C-m x C-n in the torus, and an hexagonal mesh Hc(m) x c(n), the dual of Tc-m x c(n) in the torus. It is established that sp(Tc-m x c(n)) = vd(Tc-m x c(n) = sk(Hc(m) x c(n)) = sp(Hc(m) x c(n)) = vd(Hc(m) x c(n)) = min{m, n} and that sk(Tc-m x c(n)) = 2 min {m, n}. |
Year | Venue | Keywords |
|---|---|---|
2009 | ARS COMBINATORIA | topological graph theory,graph drawing,toroidal mesh,planarity |
Field | DocType | Volume |
Discrete mathematics,Combinatorics,Polygon mesh,Skewness,Vertex (geometry),Toroid,Mathematics | Journal | 92 |
ISSN | Citations | PageRank |
0381-7032 | 0 | 0.34 |
References | Authors | |
0 | 6 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Candido Ferreira Xavier de Mendonça Neto | 1 | 17 | 4.33 |
| A. A. Constantino | 2 | 0 | 0.34 |
| Erico F. Xavier | 3 | 0 | 1.01 |
| Jorge Stolfi | 4 | 1559 | 296.06 |
| Luerbio Faria | 5 | 133 | 20.98 |
| C. M. H. de Figueiredo | 6 | 68 | 6.91 |