Schnyder Woods and Orthogonal Surfaces

In this paper we study connections between planar graphs, Schnyder woods, and orthogonal surfaces. Schnyder woods and the face counting approach have important applications in graph drawing and the dimension theory of orders. Orthogonal surfaces explain connections between these seemingly unrelated notions. We use these connections for an intuitive proof of the Brightwell-Trotter Theorem which says, that the face lattice of a 3-polytope minus one face has order dimension three. Our proof yields a linear time algorithm for the construction of the three linear orders that realize the face lattice. Coplanar orthogonal surfaces are in correspondence with a large class of convex straight line drawings of 3-connected planar graphs. We show that Schnyder’s face counting approach with weighted faces can be used to construct all coplanar orthogonal surfaces and hence the corresponding drawings. Appropriate weights are computable in linear time.     

Schnyder Woods for Higher Genus Triangulated Surfaces,with Applications to Encoding

Schnyder woods are a well-known combinatorial structure for plane triangulations, which yields a decomposition into three spanning trees. We extend here definitions and algorithms for Schnyder woods to closed orientable surfaces of arbitrary genus. In particular, we describe a method to traverse a triangulation of genus g and compute a so-called g-Schnyder wood on the way. As an application, we give a procedure to encode a triangulation of genus g and n vertices in 4n+O(glog (n)) bits. This matches the worst-case encoding rate of Edgebreaker in positive genus. All the algorithms presented here have execution time O((n+g)g) and hence are linear when the genus is fixed. Extended version of the article appeared in the Proc. of the ACM SoCG 2008. Part of the first author’s work was done during his visit to the CS Department of Université Libre de Bruxelles (Belgium).     

Tropical hyperelliptic curves

We study the locus of tropical hyperelliptic curves inside the moduli space of tropical curves of genus g. We define a harmonic morphism of metric graphs and prove that a metric graph is hyperelliptic if and only if it admits a harmonic morphism of degree 2 to a metric tree. This generalizes the work of Baker and Norine on combinatorial graphs to the metric case. We then prove that the locus of 2-edge-connected genus g tropical hyperelliptic curves is a (2g?1)-dimensional stacky polyhedral fan whose maximal cells are in bijection with trees on g?1 vertices with maximum valence 3. Finally, we show that the Berkovich skeleton of a classical hyperelliptic plane curve satisfying a certain tropical smoothness condition is a standard ladder of genus g.     

Geodesic Embeddings and Planar Graphs

Schnyder labelings are known to have close links to order dimension and drawings of planar graphs. It was observed by Ezra Miller that geodesic embeddings of planar graphs are another class of combinatorial or geometric objects closely linked to Schnyder labelings. We aim to contribute to a better understanding of the connections between these objects. In this article we prove • a characterization of 3-connected planar graphs as those graphs admitting rigid geodesic embeddings, • a bijection between Schnyder labelings and rigid geodesic embeddings, • a strong version of the Brightwell–Trotter theorem. This revised version was published online in June 2006 with corrections to the Cover Date.     

Area-efficient planar straight-line drawings of outerplanar graphs

It is important to minimize the area of a drawing of a graph, so that the drawing can fit in a small drawing-space. It is well-known that a planar graph with n vertices admits a planar straight-line grid drawing with O(n²) area [H. de Fraysseix, J. Pach, R. Pollack, How to draw a planar graph on a grid, Combinatorica 10(1) (1990) 41-51; W. Schnyder, Embedding planar graphs on the grid, in: Proceedings of the First ACM-SIAM Symposium on Discrete Algorithms, 1990, pp. 138-148]. Unfortunately, there is a matching lower-bound of Ω(n²) on the area-requirements of the planar straight-line grid drawings of certain planar graphs. Hence, it is important to investigate important categories of planar graphs to determine if they admit planar straight-line grid drawings with o(n²) area.In this paper, we investigate an important category of planar graphs, namely, outerplanar graphs. We show that an outerplanar graph G with degree d admits a planar straight-line grid drawing with area O(dn^1.48) in O(n) time. This implies that if d=o(n^0.52), then G can be drawn in this manner in o(n²) area.     

A bijection for covered maps, or a shortcut between Harer-Zagier?s and Jackson?s formulas

We consider maps on orientable surfaces. A map is called unicellular if it has a single face. A covered map is a map (of genus g) with a marked unicellular spanning submap (which can have any genus in {0,1,…,g}). Our main result is a bijection between covered maps with n edges and genus g and pairs made of a plane tree with n edges and a unicellular bipartite map of genus g with n+1 edges. In the planar case, covered maps are maps with a marked spanning tree and our bijection specializes into a construction obtained by the first author in Bernardi (2007) [4].Covered maps can also be seen as shuffles of two unicellular maps (one representing the unicellular submap, the other representing the dual unicellular submap). Thus, our bijection gives a correspondence between shuffles of unicellular maps, and pairs made of a plane tree and a unicellular bipartite map. In terms of counting, this establishes the equivalence between a formula due to Harer and Zagier for general unicellular maps, and a formula due to Jackson for bipartite unicellular maps.We also show that the bijection of Bouttier, Di Francesco and Guitter (2004) [8] (which generalizes a previous bijection by Schaeffer, 1998 [33]) between bipartite maps and so-called well-labeled mobiles can be obtained as a special case of our bijection.     

The maximum interval number of graphs with given genus

The interval number of a graph G, denoted i(G), is the least positive integer t such that G is the intersection graph of sets, each of which is the union of t compact real intervals. It is known that every planar graph has interval number at most 3 and that this result is best possible. We investigate the maximum value of the interval number for graphs with higher genus and show that the maximum value of the interval number of graphs with genus g is between ?√g? and 3 + ?√3g?. We also show that the maximum arboricity of graphs with genus g is either 1 + ?√3g? or 2 + ?√3g?.     

Boxicity of Graphs on Surfaces

The boxicity of a graph G = (V, E) is the least integer k for which there exist k interval graphs G _i  = (V, E _i ), 1 ≤ i ≤ k, such that ${E = E_1 \cap \cdots \cap E_k}$ . Scheinerman proved in 1984 that outerplanar graphs have boxicity at most two and Thomassen proved in 1986 that planar graphs have boxicity at most three. In this note we prove that the boxicity of toroidal graphs is at most 7, and that the boxicity of graphs embeddable in a surface Σ of genus g is at most 5g + 3. This result yields improved bounds on the dimension of the adjacency poset of graphs on surfaces.     

Triangle Contact Representations and Duality

A?contact representation by triangles of a graph is a set of triangles in the plane such that two triangles intersect on at most one point, each triangle represents a vertex of the graph and two triangles intersects if and only if their corresponding vertices are adjacent. De Fraysseix, Ossona de Mendez and Rosenstiehl proved that every planar graph admits a contact representation by triangles. We strengthen this in terms of a simultaneous contact representation by triangles of a planar map and of its dual. A?primal?Cdual contact representation by triangles of a planar map is a contact representation by triangles of the primal and a contact representation by triangles of the dual such that for every edge uv, bordering faces f and g, the intersection between the triangles corresponding to u and v is the same point as the intersection between the triangles corresponding to f and g. We prove that every 3-connected planar map admits a primal?Cdual contact representation by triangles. Moreover, the interiors of the triangles form a tiling of the triangle corresponding to the outer face and each contact point is a corner of exactly three triangles. Then we show that these representations are in one-to-one correspondence with generalized Schnyder woods defined by Felsner for 3-connected planar maps.     

Distributional Limits of Riemannian Manifolds and Graphs with Sublinear Genus Growth

In Benjamini and Schramm [BS01] introduced the notion of distributional limit of a sequence of graphs with uniformly bounded valence and studied such limits in the case that the involved graphs are planar. We investigate distributional limits of sequences of Riemannian manifolds with bounded curvature which satisfy a quasi-conformal condition. We then apply our results to somewhat improve Benjamini’s and Schramm’s original result on the recurrence of the simple random walk on limits of planar graphs. For instance, as an application we give a proof of the fact that for graphs in an expander family, the genus of each graph is bounded from below by a linear function of the number of vertices.     

Graphs of given genus and arbitrarily large maximum genus

The maximum genus of a connected graph G is the maximum among the genera of all compact orientable 2-manifolds upon which G has 2-cell embeddings. In the theorems that follow the use of an edge-adding technique is combined with the well-known Edmonds' technique to produce the desired results. Planar graphs of arbitrarily large maximum genus are displayed in Theorem 1. Theorem 2 shows that the possibility for arbitrarily large difference between genus and maximum genus is not limited to planar graphs. In particular, we show that the wheel graph, the standard maximal planar graph, and the prism graph are upper embeddable. We then show that given m and n, there is a graph of genus n and maximum genus larger than mn.     

Orthogonal Surfaces and Their CP-Orders

Orthogonal surfaces are nice mathematical objects which have interesting connections to various fields, e.g., integer programming, monomial ideals and order dimension. While orthogonal surfaces in one or two dimensions are rather trivial already the three dimensional case has a rich structure with connections to Schnyder woods, planar graphs and three-polytopes. Our objective is to detect more of the structure of orthogonal surfaces in four and higher dimensions. In particular we are driven by the question which non-generic orthogonal surfaces have a polytopal structure. We review the state of knowledge of the three-dimensional situation. On that basis we introduce terminology for higher dimensional orthogonal surfaces and continue with the study of characteristic points and the cp-orders of orthogonal surfaces, i.e., the dominance orders on the characteristic points. In the generic case these orders are (almost) face lattices of polytopes. Examples show that in general cp-orders can lack key properties of face lattices. We investigate extra requirements which may help to have cp-orders which are face lattices. Finally, we turn the focus and ask for the realizability of polytopes on orthogonal surfaces. There are criteria which prevent large classes of simplicial polytopes from being realizable. On the other hand we identify some families of polytopes which can be realized on orthogonal surfaces.      

Some isomorphism results for Thompson-like groups <Emphasis Type="Italic">V</Emphasis><Subscript><Emphasis Type="Italic">n</Emphasis></Subscript>(<Emphasis Type="Italic">G</Emphasis>)

The natural automorphism group of a translation surface is its group of translations. For finite translation surfaces of genus g ≥ 2 the order of this group is naturally bounded in terms of g due to a Riemann–Hurwitz formula argument. In analogy with classical Hurwitz surfaces, we call surfaces which achieve the maximal bound Hurwitz translation surfaces. We study for which g there exist Hurwitz translation surfaces of genus g.     

Weak embedding of planar graphs

A weak embedding of a graphG is an embedding ofG with all the faces being tours. In this paper, for some planar graphs the weak maximum genus of them are given. And for the planar graphG, a characterization of whetherG can be weakly embedded on the nonspherical surfaces is obtained.     

Gluings of surfaces with polygonal boundaries

By pairwise gluing edges of a polygon, one obtains two-dimensional surfaces with handles and holes. We compute the number N _g,L (n ₁, ..., n _L ) of distinct ways to obtain a surface of given genus g whose boundary consists of L polygonal components with given numbers n ₁, ..., n _L of edges. Using combinatorial relations between graphs on real two-dimensional surfaces, we derive recursion relations between the N _g,L . We show that the Harer-Zagier numbers arise as a special case of N _g,L and derive a new closed-form expression for them.     

The dominating set problem is fixed parameter tractable for graphs of bounded genus

We describe an algorithm for the dominating set problem with time complexity O((4g+40)^kn²) for graphs of bounded genus g1, where k is the size of the set. It has previously been shown that this problem is fixed parameter tractable for planar graphs. We give a simpler proof for the previous O(8^kn²) result for planar graphs. Our method is a refinement of the earlier techniques.     

Simplification of formulas for the number of maps on surfaces

Two combinatorial identities obtained by the author are used to simplify formulas for the number of general rooted cubic planar maps, for the number of g-essential maps on surfaces of small genus, and also for rooted Eulerian maps on the projective plane. Besides, an asymptotics for the number of maps with a large number of vertices is obtained.     

Irreducible Triangulations of Surfaces with Boundary

A triangulation of a surface is irreducible if no edge can be contracted to produce a triangulation of the same surface. In this paper, we investigate irreducible triangulations of surfaces with boundary. We prove that the number of vertices of an irreducible triangulation of a (possibly non-orientable) surface of genus g ≥ 0 with b ≥ 0 boundary components is O(g + b). So far, the result was known only for surfaces without boundary (b = 0). While our technique yields a worse constant in the O(.) notation, the present proof is elementary, and simpler than the previous ones in the case of surfaces without boundary.     

Counting alternating knots by genus

It is shown that the number of alternating knots of given genus g>1 grows as a polynomial of degree 6g−4 in the crossing number. The leading coefficient of the polynomial, which depends on the parity of the crossing number, is related to planar trivalent graphs with a Bieulerian path. The rate of growth of the number of such graphs is estimated.     

A separator theorem for graphs of bounded genus

Many divide-and-conquer algorithms on graphs are based on finding a small set of vertices or edges whose removal divides the graph roughly in half. Most graphs do not have the necessary small separators, but some useful classes do. One such class is planar graphs: If an n-vertex graph can be drawn on the plane, then it can be bisected by removal of O(sqrt(n)) vertices (R. J. Lipton and R. E. Tarjan, SIAM J. Appl. Math.36 (1979), 177–189). The main result of the paper is that if a graph can be drawn on a surface of genus g, then it can be bisected by removal of O(sqrt(gn)) vertices. This bound is best possible to within a constant factor. An algorithm is given for finding the separator that takes time linear in the number of edges in the graph, given an embedding of the graph in its genus surface. Some extensions and applications of these results are discussed.