We provide a framework for the design and analysis of dynamic programming algorithms for surface-embedded graphs on n vertices and branchwidth at most k. Our technique applies to general families of ...problems where standard dynamic programming runs in \documentclass12pt{minimal}
\usepackage{amsmath}
\usepackage{wasysym}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsbsy}
\usepackage{mathrsfs}
\usepackage{upgreek}
\setlength{\oddsidemargin}{-69pt}
\begin{document}$2^{\mathcal{O}(k\cdot \log k)}\cdot n$\end{document} steps. Our approach combines tools from topological graph theory and analytic combinatorics. In particular, we introduce a new type of branch decomposition called surface cut decomposition, capturing how partial solutions can be arranged on a surface. Then we use singularity analysis over expressions obtained by the symbolic method to prove that partial solutions can be represented by a single-exponential (in the branchwidth k) number of configurations. This proves that, when applied on surface cut decompositions, dynamic programming runs in \documentclass12pt{minimal}
\usepackage{amsmath}
\usepackage{wasysym}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsbsy}
\usepackage{mathrsfs}
\usepackage{upgreek}
\setlength{\oddsidemargin}{-69pt}
\begin{document}$2^{\mathcal{O}(k)}\cdot n$\end{document} steps. That way, we considerably extend the class of problems that can be solved in running times with a single-exponential dependence on branchwidth and unify/improve all previous results in this direction.
Embedding graphs on the torus is a problem with both theoretical and practical importance. It is required to embed a graph on the torus for solving many application problems such as VLSI design, ...graph drawing and etc. Polynomial time and exponential time algorithms for embedding graphs on the torus are known. However, the polynomial time algorithms are very complex and their implementation has been a challenge for a long time. On the other hand, the implementations of some exponential time algorithms are known but they are not efficient for large graphs in practice. To develop an efficient practical tool for embedding graphs on the torus, we propose a new exponential time algorithm for embedding graphs on the torus. Compared with a well used previous exponential time algorithm, our algorithm has a better practical running time.
In this paper we give a linear algorithm to edge partition a toroidal graph, i.e., graph that can be embedded on the orientable surface of genus one without edge crossing, into three forests plus a ...set of at most three edges. For triangulated toroidal graphs, this algorithm gives a linear algorithm for finding three edge-disjoint spanning trees. This is in a certain way an extension of the well-known algorithm of Schnyder's decomposition for planar graph.
In ``A survey on the Turaev genus of knots'', Champanerkar and Kofman propose several open questions. The first asks whether the polynomial whose coefficients count the number of quasi-trees of the ...all-A ribbon graph obtained from a diagram with minimal Turaev genus is an invariant of the knot. We answer negatively by showing a counterexample obtained from the two diagrams of on the Knot Atlas and KnotScape.
In this work, we expose four bijections each allowing to increase (or decrease) one parameter in either uniform random forests with a fixed number of edges and trees, or quadrangulations with a ...boundary having a fixed number of faces and a fixed boundary length. In particular, this gives a way to sample a uniform quadrangulation with n+1 faces from a uniform quadrangulation with n faces or a uniform forest with n+1 edges and p trees from a uniform forest with n edges and p trees.
PDF
