Embedding digraphs on orientable surfaces
The topic of embeddings of directed graphs considered in this article is a restriction of the problem of (general) graph embeddings on orientable surfaces. The digraphs under consideration must be Eulerian, and their embeddings are to be 2-cell embeddings on orientable surfaces satisfying the additional property that the arcs on the boundary of every region must all point in the same direction (i.e., the boundary of every region is an oriented circuit of the underlying digraph). The authors investigate several analogs of the classical graph embedding problems, and obtain a surprising number of interesting general results. They show, for example, that under these restrictions, the genus list (the list of all possible genera of surfaces admitting an embedding) of any digraph is an unbroken interval of integers, and characterize regular digraphs \(D\) of in- and out-degree 2 that admit an embedding with exactly two regions (if and only if \(D\) admits two Euler circuits with no common pair of consecutive arcs). They also construct a family of digraphs with an increasing minimal number of regions, a family of digraphs with an unbounded genus range, and a family of digraphs that shows that the minimum genus can be arbitrarily large while the embedding range remains 1 (a result that differs from the case of general graph embeddings). They also show that both the minimum and maximum genus of a digraph may be arbitrarily different from the minimum and maximum genus of the corresponding underlying graph. In their final result, the authors determine the maximum genus of every regular tournament by showing that every regular tournament can be embedded with two or three regions.
- Compatible Euler tours for transition systems in Eulerian graphs
- Exponential families of non-isomorphic triangulations of complete graphs
- Face 2-colourable triangular embeddings of complete graphs
- Genus distributions for bouquets of circles
- How to determine the maximum genus of a graph
- scientific article; zbMATH DE number 4006288 (Why is no real title available?)
- scientific article; zbMATH DE number 3739583 (Why is no real title available?)
- scientific article; zbMATH DE number 15460 (Why is no real title available?)
- scientific article; zbMATH DE number 1156577 (Why is no real title available?)
- scientific article; zbMATH DE number 3257167 (Why is no real title available?)
- Maps and -matroids
- On the maximum number of pairwise compatible euler cycles
- Orthogonal A-trails of 4-regular graphs embedded in surfaces of low genus
- The Genus, Regional Number, and Betti Number of a Graph
- The graph genus problem is NP-complete
- The directed genus of the de Bruijn graph
- Embeddings of 4-valent framed graphs into 2-surfaces
- A note on directed genera of some tournaments
- Obstructions to directed embeddings of Eulerian digraphs in the plane
- A character approach to directed genus distribution of graphs: the bipartite single-black-vertex case
- Embedding grid graphs on surfaces
- Enumeration of digraph embeddings
- The genus distributions of directed antiladders in orientable surfaces
- Genera of Cayley maps
- Book embedding of locally planar graphs on orientable surfaces
- Growth rates of groups associated with face 2-coloured triangulations and directed Eulerian digraphs on the sphere
- Checkerboard embeddings of *-graphs into nonorientable surfaces
- The genus distributions of 4-regular digraphs
- Polyhedral embeddings of snarks in orientable surfaces
- Whitney's theorem for 2-regular planar digraphs
- Embedding quartic Eulerian digraphs on the plane
- Log-concavity of the genus polynomials of Ringel ladders
- \(Z\)-oriented triangulations of surfaces
- scientific article; zbMATH DE number 7535271 (Why is no real title available?)
- Enumerating graph embeddings and partial-duals by genus and Euler genus
- scientific article; zbMATH DE number 5584098 (Why is no real title available?)
- Partially broken orientations of Eulerian graphs on closed surfaces
- A duality for labeled graphs and factorizations with applications to graph embeddings and Hurwitz enumeration
- Counting orientable embeddings by genus for a type of 3-regular graph
- Pre-signed graphs: a reformulation of signed graphs and their embeddings
- A theorem for the maximum genus of a digraph
- Bi-eulerian embeddings of graphs and digraphs
- The genus polynomials of cross-ladder digraphs in orientable surfaces
This page was built for publication: Embedding digraphs on orientable surfaces
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1850600)
