Name
Abstract | ||
|---|---|---|
Schnyder woods are a well known combinatorial structure for planar graphs, which yields a decomposition into 3 vertex-spanning trees. Our goal is to extend definitions and algorithms for Schnyder woods 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. First, we define a new traversal order of the vertices of a triangulated surface of genus g together with an orientation and coloration of the edges that extends the one proposed by Schnyder for the planar case. As a by-product we show how some recent schemes for compression and compact encoding of graphs can be extended to higher genus. All the algorithms presented here have linear time complexity. |
Year | DOI | Venue |
|---|---|---|
2008 | 10.1145/1377676.1377730 | Symposium on Computational Geometry 2013 |
Keywords | Field | DocType |
triangulated surface,planar case,arbitrary genus,schnyder wood,planar graph,linear time complexity,compact encoding,combinatorial structure,general case,new traversal order,higher genus,graph embedding,spanning tree,linear time | Discrete mathematics,Graph,Combinatorics,Tree traversal,Vertex (geometry),Planar,Triangulation,Genus (mathematics),Time complexity,Mathematics,Planar graph | Conference |
Citations | PageRank | References |
0 | 0.34 | 26 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Luca Castelli Aleardi | 1 | 87 | 7.96 |
| Eric Fusy | 2 | 22 | 2.40 |
| Thomas Lewiner | 3 | 700 | 43.70 |