Name
Abstract | ||
|---|---|---|
We study a well known characterization of planar graphs, also called Schnyder wood or Schnyder labelling, which yields a decomposition into vertex spanning trees. The goal is to extend previous algorithms and characterizations designed for planar graphs (corresponding to combinatorial surfaces with the topology of the sphere, i.e., of genus 0) to the more general case of graphs embedded on surfaces of arbitrary genus. We define a new traversal order of the vertices of a triangulated surface of genus g together with an orientation and colouration of the edges that extends the one proposed by Schnyder for the planar case. As a by-product we show how to characterize our edge coloration in terms of genus g maps. |
Year | DOI | Venue |
|---|---|---|
2008 | 10.1016/j.endm.2008.06.022 | Electronic Notes in Discrete Mathematics |
Keywords | Field | DocType |
Schnyder trees,triangulations,higher genus surfaces | Discrete mathematics,Graph,Combinatorics,Tree traversal,Vertex (geometry),Triangulation,Planar,Spanning tree,Genus (mathematics),Mathematics,Planar graph | Journal |
Volume | ISSN | Citations |
31 | 1571-0653 | 0 |
PageRank | References | Authors |
0.34 | 7 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Luca Castelli Aleardi | 1 | 87 | 7.96 |
| Éric Fusy | 2 | 198 | 21.95 |
| Thomas Lewiner | 3 | 700 | 43.70 |