Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userFrom unicellular fatgraphs to trees
78
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
In this paper we study the minimum number of reversals needed to transform a unicellular fatgraph into a tree. We consider reversals acting on boundary components, having the natural interpretation as gluing, slicing or half-flipping of vertices. Our main result is an expression for the minimum number of reversals needed to transform a unicellular fatgraph to a plane tree. The expression involves the Euler genus of the fatgraph and an additional parameter, which counts the number of certain orientable blocks in the decomposition of the fatgraph. In the process we derive a constructive proof of how to decompose non-orientable, irreducible, unicellular fatgraphs into smaller fatgraphs of the same type or trivial fatgraphs, consisting of a single ribbon. We furthermore provide a detailed analysis how reversals affect the component-structure of the underlying fatgraphs. Our results generalize the Hannenhalli-Pevzner formula for the reversal distance of signed permutations.
rate research
Read More
The modular decomposition of a symmetric map $deltacolon Xtimes X to Upsilon$ (or, equivalently, a set of symmetric binary relations, a 2-structure, or an edge-colored undirected graph) is a natural construction to capture key features of $delta$ in labeled trees. A map $delta$ is explained by a vertex-labeled rooted tree $(T,t)$ if the label $delta(x,y)$ coincides with the label of the last common ancestor of $x$ and $y$ in $T$, i.e., if $delta(x,y)=t(mathrm{lca}(x,y))$. Only maps whose modular decomposition does not contain prime nodes, i.e., the symbolic ultrametrics, can be exaplained in this manner. Here we consider rooted median graphs as a generalization to (modular decomposition) trees to explain symmetric maps. We first show that every symmetric map can be explained by extended hypercubes and half-grids. We then derive a a linear-time algorithm that stepwisely resolves prime vertices in the modular decomposition tree to obtain a rooted and labeled median graph that explains a given symmetric map $delta$. We argue that the resulting tree-like median graphs may be of use in phylogenetics as a model of evolutionary relationships.
The $ell$-deck of a graph $G$ is the multiset of all induced subgraphs of $G$ on $ell$ vertices. In 1976, Giles proved that any tree on $ngeq 6$ vertices can be reconstructed from its $ell$-deck for $ell geq n-2$. Our main theorem states that it is enough to have $ellgeq (8/9+o(1))n$, making substantial progress towards a conjecture of Nydl from 1990. In addition, we can recognise connectedness from the $ell$-deck if $ellgeq 9n/10$, and reconstruct the degree sequence from the $ell$-deck if $ellge sqrt{2nlog(2n)}$. All of these results are significant improvements on previous bounds.
In this paper, we introduce the notion of the quadratic graph, that is a graph whose eigenvalues are integral or quadratic algebraic integral, and determine nine infinite families of quadratic starlike trees, which are just all the quadratic starlike trees including integral starlike trees. Thus the quadratic starlike trees are completely characterized, and moreover, the display expressions for the characteristic polynomials of the quadratic starlike trees are also given.
We present a bijection between some quadrangular dissections of an hexagon and unrooted binary trees, with interesting consequences for enumeration, mesh compression and graph sampling. Our bijection yields an efficient uniform random sampler for 3-connected planar graphs, which turns out to be determinant for the quadratic complexity of the current best known uniform random sampler for labelled planar graphs [{bf Fusy, Analysis of Algorithms 2005}]. It also provides an encoding for the set $mathcal{P}(n)$ of $n$-edge 3-connected planar graphs that matches the entropy bound $frac1nlog_2|mathcal{P}(n)|=2+o(1)$ bits per edge (bpe). This solves a theoretical problem recently raised in mesh compression, as these graphs abstract the combinatorial part of meshes with spherical topology. We also achieve the {optimal parametric rate} $frac1nlog_2|mathcal{P}(n,i,j)|$ bpe for graphs of $mathcal{P}(n)$ with $i$ vertices and $j$ faces, matching in particular the optimal rate for triangulations. Our encoding relies on a linear time algorithm to compute an orientation associated to the minimal Schnyder wood of a 3-connected planar map. This algorithm is of independent interest, and it is for instance a key ingredient in a recent straight line drawing algorithm for 3-connected planar graphs [bf Bonichon et al., Graph Drawing 2005].
In this short note, we first present a simple bijection between binary trees and colored ternary trees and then derive a new identity related to generalized Catalan numbers.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
