Geometric representations and symmetries of graphs, maps and other discrete structures and applications in science

• Applicant: Professor Dr. Peter Florian Stadler
• Subject Area: Theoretical Computer Science
• Term: from 2011 to 2015
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 195353141

• Final Report Year: 2019

Final Report Abstract

The main results of the project are: - Explorations of the connection between the geometric graph models of molecules and polymers and the graphs that represent the relationships among them - A survey of hypergraph products has been published. - Characterization of retracts of Cartesian products of chordal graphs. - Uniqueness of prime factorization of thin hypergraphs w.r.t. strong products has been proved and factorization algorithm is given. - Characterization of recombination on strings as transit function was obtained. - A unified framework for linear and circular multiple sequence alignments was established. - A new formalization of graph editing, relaxed square property and topology of elementary cycles, connective spaces and application is landscape theory were studied. - An explicit construction of a minimum cycle bases for the lexicographic product of graphs. - Application of redundant non-invertible encodings in hard combinatorial optimizaton problems - An efficient heuristic for constructing alternative local multiple sequence alignments from a collection of local pairwise alignments developed, tested.

Publications

• Classification of regular maps of Euler characteristic $-3p$.J. Combin. Theory Ser. B 102 (2012), 967-981
  Conder, Marston and Nedela, Roman and Siran, Jozef
  
• Dendrimers are the unique chemical trees with maximum spectral radius. MATCH 68 (2012), 851-854
  Biyikoglu, Turker and Leydold, Josef
  
• On graph identfcaton problems and the special case of identfying vertces using paths. IWOCA 2012: Combinatorial Algorithms, pp. 32-45.
  Foucaud, Florent, Kovse, Matjaz
  
• The Clique Problem in Ray Intersection Graphs, Algorithms - ESA 2012, Lecture Notes in Computer Science Volume 7501, 2012, pp 241-252
  Sergio Cabello, Jean Cardinal, Stefan Langerman
  
• Computing the stretch of an embedded graph. SIAM journal on discrete mathematics, ISSN 0895-4801, 2014, vol. 28, no. 3, str. 1391-1401
  Cabello S., Chimani M., Hlineny P.
  
• Strong products of hypergraphs: Unique prime factorizaton theorems and algorithms. Discrete Applied Mathematics, Vol. 171. 2014, pp. 60-71.
  Hellmuth, Marc, Noll, Manuel, Ostermeier, Lydia
  
• Unique Square Property, Equitable Parttons, and Product-li e Graphs. Discrete Mathematics, Vol. 320. 2014, pp. 92-103.
  Hellmuth, Marc, Ostermeier, Lydia, Stadler, Peter F.
  
• „A note on graphs whose largest eigenvalues of the modularity matrix equals zero", Electronic Journal of Linear Algebra vol 27, 256 (2014)
  S. Majstorovic, D. Stevanovic
  
• Connectvity Spaces. Mathematics in Computer Science, Vol. 9. 2015, pp. 409–436.
  Stadler, Bärbel M. R., Stadler, Peter F.
  
• Generalized Topologies: hypergraphs, chemical reactons, and biological evoluton. Advances in Mathematical Chemistry and Applications, Vol. 2. 2015, pp. 300-328.
  Flamm, Christoph, Stadler, Bärbel M. R.
  
• The Grid Property, and Product-li e Hypergraphs. Graphs and Combinatorics, Vol. 31. 2015, pp.757–770.
  Ostermeier, Lydia, Stadler, Peter F.
  
• The Relaxed Square Property. Australian Journal of Combinatorics, Vol. 62. 2015, Issue 3, pp. 240–270.
  Hellmuth, Marc, Marc, Tilen, Ostermeier, Lydia, Stadler, Peter F.