Workshop B2 - Graph Theory and Combinatorics

Organizers: Marc Noy (Universitat Politècnica de Catalunya, Spain) - Jaroslav Nesetril (Charles University, Czech Republic) - Angelika Steger (ETH Zürich, Switzerland)

View workshop abstracts PDF



No abstracts.



Scaffolding skeletons using spherical Voronoi diagrams

Alvaro Javier Fuentes Suárez

Inria Sophia Antipolis, France   -

Skeletons are used in 3D graphics for modeling and animating articulated shapes. The user can design a complex shape by sketching a simple and intuitive geometric object that is the input to a surface generating algorithm.

In this work, a skeleton is a finite set of line segments in space that do not intersect except at the endpoints. It can be seen as a graph with geometrical constraints (length of the edges, position of vertices). We study the problem of generating a mesh around a skeleton. The mesh we want to obtain should be as "coarse" as possible (in the sense of number of patches around each line segment), with mostly quad patches and must enclose the skeleton. Following [Panotopoulou] we call this mesh a scaffold.

This problem has been studied before in [Ji2010] and [Bærentzen2012]. The main limitation in Ji et al. was the presence of irregularities in the final mesh. Furthermore the method proposed by Bærentzen et al. cannot handle closed skeletons, i.e. skeletons with cycles when seen as a graph. The following problems were also left as open : under what conditions the construction can be done; whether there is an optimal solution on the number of patches; or whether the mesh can be constructed such that each segment piece is enclosed by the same number of patches.

We present a method for constructing a scaffold for a skeleton using spherical Voronoi diagrams at the branch points. We prove that such a mesh can always be computed, even in the presence of cycles. We can compute a solution with minimal total number of patches, or, alternatively, a mesh with the same number of patches around each line segment. The main tools we use are: spherical Voronoi diagrams, Delaunay triangulations, Integer Linear Programming and a numerical characterization of inscribable graphs due to [Rivin1996].

Our method has been implemented and is currently being used for developing a meshing algorithm for implicit surfaces defined around a skeleton [Zanni2013]. We point out also that the problem is closely related to a perfect matching for graphs.


[Panotopoulou] Panotopoulou, A., K. Welker, E. Ross and E. Hubert, "Scaffolding a Skeleton", (in preparation).

[Ji2010] Ji, Z., L. Liu and Y. Wang, "B-Mesh: A modeling system for base meshes of 3D articulated shapes", Computer Graphics Forum 29 (2010).

[Bærentzen2012] Bærentzen, J. A., M. K. Misztal and K. We?nicka, "Converting skeletal structures to quad dominant meshes", Computers and Graphics 36 (2012).

[Rivin1996] Rivin, I., "A Characterization of Ideal Polyhedra in Hyperbolic 3-Space", Annals of Mathematics 143 (1996).

[Zanni2013] Zanni, C., "Skeleton-based Implicit Modeling & Applications" Phd thesis, Universitè de Grenoble (2013).

Joint work with Evelyne Hubert (Inria Sophia Antipolis).

View abstract PDF

Counting arithmetical structures

Luis David Garcia Puente

Sam Houston State University, USA   -

Let $G$ be a finite, simple, connected graph. An arithmetical structure on $G$ is a pair of positive integer vectors $d,r$ such that $(\mathrm{diag}(d)-A)r=0$, where $A$ is the adjacency matrix of $G$. Arithmetical graphs were introduced in the context of arithmetical geometry by Lorenzini in 1989 to model intersections of curves. We investigate the combinatorics of arithmetical structures on path and cycle graphs, as well as the associated critical groups (the cokernels of the matrices $(\mathrm{diag}(d)-A))$. For paths, we prove that arithmetical structures are enumerated by the Catalan numbers, and we obtain refined enumeration results related to ballot sequences. For cycles, we prove that arithmetical structures are enumerated by the binomial coefficients $\binom{2n-1}{ n-1}$, and we obtain refined enumeration results related to multisets. In addition, we determine the critical groups for all arithmetical structures on paths and cycles.

Joint work with Benjamin Braun (University of Kentucky), Hugo Corrales (CINVESTAV), Scott Corry (Lawrence University), Darren Glass (Gettysburg College), Nathan Kaplan (University of California, Irvine), Jeremy L. Martin (University of Kansas), Gregg Musiker (University of Minnesota) and Carlos E. Valencia (CINVESTAV).

View abstract PDF

Null decomposition of trees and its concecuences

Daniel Alejandro Jaume

Universidad Nacional de San Luis, Argentina   -

The purpose of this study is to determine which information about a tree could be obtained from the support of the null space its adjacency matrices. In order to do that, we introduce a new family of trees, the S-trees, which are based on the non-zero entries of vectors in null space. We show that every tree can be decomposed into a forest of S-trees and a forest of non-singular trees.

The support of a tree \(T\) is the set \[ Supp(T):=\{u \in V(T): \exists x \in \mathcal{N}(T) \text{ such that } x_{u}\neq 0\} \] Where \(\mathcal{N}(T)\) is the null space of \(A(T)\), the adjacency matrix of \(T\). The cardinality of the support is denoted \(supp(T)\).

Definition: A tree \(T\) is an S-tree if \(N\left[ Supp(T) \right]=V(T) \), where \(N[Supp(T)]\) is the closed neighborhood of \(Supp(T)\).

Definition: Let \(T\) be an S-tree. The core of \(T\), denoted by \(Core(T)\), is defined to be the set of all non-supported vertices of \(T\). We will denote by \(core(T)\) the cardinality of \(Core(T)\).

A tree \(T\) is non-singular tree, N-tree for short, if its adjacency matrix \(A(T)\) is invertible. Thus \(T\) is a N-tree if and only if \(T\) has a perfect matching.

Definition: Let \(T\) be a tree. The S-forest of T, denoted by \(\mathcal{F}_{S}(T)\), is defined to be the forest induced by the closed neighbor of \(Supp(T)\) in \(T\): \( \mathcal{F}_{S}(T):=T\left\langle N\left[ Supp(T) \right] \right\rangle \). The N-forest of T, denoted by \(\mathcal{F}_{N}(T)\), is defined to be the remain forest: \( \mathcal{F}_{N}(T):=T \backslash \mathcal{F}_{S}(T) \). The pair of forests \((\mathcal{F}_{S}(T),\mathcal{F}_{N}(T))\) is called the Null Decomposition of \(T\).

Theorem: Let \(T\) be a tree. The S-forest \(\mathcal{F}_{S}(T)\) of \(T\) is a forest of S-trees, and the N-forest \(\mathcal{F}_{N}(T)\) of \(T\) is a forest of N-trees. Futhermore:

1) \(\nu(T) = core(T)+\frac{|V(\mathcal{F}_{N}(T))|}{2}\), where \(\nu(T)\) is the matching number of \(T\),

2) \(\alpha(T)= supp(T)+\frac{|V(\mathcal{F}_{N}(T))|}{2} \), where \(\alpha(T)\) is the independence number of \(T\),

3) \( rk(T) = core(T)+|V(\mathcal{F}_{N}(T))| \), where \(rk(T)\) is the rank of the adjacency matrix of \(T\),

4) \( null(T) = supp(T)-core(T) \), where \(null(T)\) is the nullity of the adjacency matrix of \(T\),

5) \( m(T)=\prod_{S \in\mathcal{F}_{S}(T)} m(S) \), where \(m(T)\) is the number of maximum matching of \(T\), and

6) \( a(T)=\prod_{N \in\mathcal{F}_{N}(T)} a(N) \), where \(a(T)\) is the number of maximum independent sets of \(T\).

Corollary: Let \(T\) be a tree. Then \(\nu(T)=\alpha(T)-null(T)\).

Joint work with Gonzalo Molina (Universidad Nacional de San Luis).

View abstract PDF

Bounds on the letter frequencies in Kolakoski sequences via Chvatal's sequence of graphs

Bernd Sing

The University of the West Indies, Barbados   -

An infinite sequence $z$ over the alphabet $\{1,2\}$ that equals its own run-length sequence, is called a Kolakoski-sequence (also see [1,2]): \[% \begin{array}{ccccccccccccccc}% z\!& \!=\! & \underbrace{22} & \underbrace{11} & \underbrace{2} & \underbrace{1} & \underbrace{22} & \underbrace{1} & \underbrace{22} & \underbrace{11} & \underbrace{2} & \underbrace{11} & \ldots && \\ && 2 & 2 & 1 & 1 & 2 & 1 & 2 & 2 & 1 & 2 & \ldots &\! =\!&\! z. \end{array}% \] Prepending a 1 to this sequence gives the other Kolakoski sequence over this alphabet. Although it is conjectured that the letter frequencies are equal in the infinite sequence (i.e., half the letters are 1s and half of them 2s), it is not even know if the frequencies actually exist.

Seeking to understand this mysterious sequences better, one can consider sequences that equal their own run-length sequence over other alphabets with two letters, see [3]: For alphabets consisting of two even numbers, one can easily establish that the limiting frequencies are $1/2$; in the case of two odd numbers, the limiting frequencies are unequal (they are given by cubic irrationals); while in the case that of one even and one odd number, one arrives at the same conjecture about the letter frequencies as for the alphabet $\{1,2\}$.

In order to find bounds on the letter frequencies of the Kolakoski sequence, Vasek Chvatal [4] considered a certain recursively defined sequence of digraphs. Using the 22nd term in this sequence, he showed that the letter frequencies of the Kolakoski sequence are confined to $[0.499162,0.500838]$; however, the number of vertices grows by a factor of $2$ in each step (so the 22nd graph has $2^{22}$ vertices).

In this paper we look at the structure of the digraphs one gets for different alphabets: One can again recursively define such a sequence of digraphs for any two letter alphabet. While the number of vertices always grows by a factor of $2$, other properties like connectedness differ for different alphabets.


[1] W. Kolakoski, ``Self generating runs, Problem 5304'', Amer. Math. Monthly 72: 674 (1965).

[2] R. Oldenburger, ``Exponent trajectories in symbolic dynamics''. Trans. AMS 46: 453–466 (1939).

[3] B. Sing, ``More Kolakoski sequences'', Integers 11B (2011), A14.

[4] V. Chvatal, ``Notes on the Kolakoski sequence'', DIMACS Technical Report 93-84 (1994).

View abstract PDF

The Dehn-Sommerville Relations and the Catalan Matroid

Nicole Yamzon

San Francisco State University, United States   -

The $f$-vector of a $d$-dimensional polytope $P$ stores the number of faces of each dimension. When $P$ is simplicial the Dehn--Sommerville relations imply that to determine the $f$-vector of $P$, we only need to know approximately half of its entries. This raises the question: Which $(\lceil{\frac{d+1}{2}}\rceil)$-subsets of the $f$-vector of a general simplicial polytope are sufficient to determine the whole $f$-vector? We prove that the answer is given by the bases of the Catalan matroid.

Joint work with Anastasia Chavez (University of California Berkeley).

View abstract PDF

FoCM 2017, based on a nodethirtythree design.