More Like this

1. Maximal Chains in Bond Lattices

   https://doi.org/10.37236/10983  

   Ahirwar, Shreya; Fishel, Susanna; Gya, Parikshita; Harris, Pamela; Pham, Nguyen; Vindas Meléndez, Andrés; Vo, Dan Khanh (July 2022, The Electronic Journal of Combinatorics)

   Let $$G$$ be a graph with vertex set $$\{1,2,\ldots,n\}$$. Its bond lattice, $BL(G)$, is a sublattice of the set partition lattice. The elements of $BL(G)$ are the set partitions whose blocks induce connected subgraphs of $$G$$. In this article, we consider graphs $$G$$ whose bond lattice consists only of noncrossing partitions. We define a family of graphs, called triangulation graphs, with this property and show that any two produce isomorphic bond lattices. We then look at the enumeration of the maximal chains in the bond lattices of triangulation graphs. Stanley's map from maximal chains in the noncrossing partition lattice to parking functions was our motivation. We find the restriction of his map to the bond lattice of certain subgraphs of triangulation graphs. Finally, we show the number of maximal chains in the bond lattice of a triangulation graph is the number of ordered cycle decompositions. 

   more » « less
2. Splittable Spanning Trees and Balanced Forests in Dense Random Graphs

   Gillman, David; Platnick, Jacob; Randall, Dana (April 2026, Latin American Theoretical Informatics (LATIN) 2026)

   We consider the probability that a spanning tree chosen uniformly at random from a graph can be partitioned into a fixed number k of trees of equal size with the removal of k − 1 edges. In that case, the spanning tree is called splittable. Splittable spanning trees are useful in algorithms for sampling balanced forests, forests whose components are of equal size, and for sampling partitions of a graph into components of equal size, with applications in redistricting, network algorithms, and image decomposition. Cannon et al. recently showed that spanning trees on grid graphs and grid-like graphs on n vertices are splittable into k equal sized components with probability at least n−2k, leading to the first rigorous sampling algorithm for balanced forests for any class of graphs. Focusing on the complementary case of dense random graphs, we show that random spanning trees again have inverse polynomial probability of being splittable; specifically, a random spanning tree is splittable with probability at least n(−k/2) for both the G(n, p) and G(n, m) models when p = Ω(1/ log n), giving the first dense class of graphs where partitions of equal size can be sampled efficiently. In addition, we present an infinite family of graphs with properties that have been conjectured to ensure splittability (i.e., Hamiltonian subgraphs of the triangular lattice) and prove that random spanning trees are not splittable with more than an exponentially small probability. As a consequence of this, we show that a family of widely-used Markov chain algorithms for sampling partitions of equal size will fail on this family of graphs if their state spaces are restricted to equal-size partitions. Moreover, we show these algorithms will be inefficient if their state spaces are generalized to include any unbalanced partitions, suggesting barriers for sampling balanced partitions in other classes of sparse graphs. 

   more » « less
3. RASMA: a reverse search algorithm for mining maximal frequent subgraphs

   https://doi.org/10.1186/s13040-021-00250-1  

   Salem, Saeed; Alokshiya, Mohammed; Hasan, Mohammad Al (December 2021, BioData Mining)

   Abstract Background Given a collection of coexpression networks over a set of genes, identifying subnetworks that appear frequently is an important research problem known as mining frequent subgraphs. Maximal frequent subgraphs are a representative set of frequent subgraphs; A frequent subgraph is maximal if it does not have a super-graph that is frequent. In the bioinformatics discipline, methodologies for mining frequent and/or maximal frequent subgraphs can be used to discover interesting network motifs that elucidate complex interactions among genes, reflected through the edges of the frequent subnetworks. Further study of frequent coexpression subnetworks enhances the discovery of biological modules and biological signatures for gene expression and disease classification. Results We propose a reverse search algorithm, called RASMA, for mining frequent and maximal frequent subgraphs in a given collection of graphs. A key innovation in RASMA is a connected subgraph enumerator that uses a reverse-search strategy to enumerate connected subgraphs of an undirected graph. Using this enumeration strategy, RASMA obtains all maximal frequent subgraphs very efficiently. To overcome the computationally prohibitive task of enumerating all frequent subgraphs while mining for the maximal frequent subgraphs, RASMA employs several pruning strategies that substantially improve its overall runtime performance. Experimental results show that on large gene coexpression networks, the proposed algorithm efficiently mines biologically relevant maximal frequent subgraphs. Conclusion Extracting recurrent gene coexpression subnetworks from multiple gene expression experiments enables the discovery of functional modules and subnetwork biomarkers. We have proposed a reverse search algorithm for mining maximal frequent subnetworks. Enrichment analysis of the extracted maximal frequent subnetworks reveals that subnetworks that are frequent are highly enriched with known biological ontologies. 

   more » « less
4. The QuaSEFE Problem

   Angelini, P.; Forster, H.; Hoffmann, M.; Kaufmann, M.; Kobourov, S.; Liotta, G.; Patrigniani, M. (January 2019, International Symposium on Graph Drawing and Network Visualization)

   We initiate the study of Simultaneous Graph Embedding with Fixed Edges in the beyond planarity framework. In the QSEFE problem, we allow edge crossings, as long as each graph individually is drawn quasiplanar, that is, no three edges pairwise cross. %We call this problem the QSEFE problem. We show that a triple consisting of two planar graphs and a tree admit a QSEFE. This result also implies that a pair consisting of a 1-planar graph and a planar graph admits a QSEFE. We show several other positive results for triples of planar graphs, in which certain structural properties for their common subgraphs are fulfilled. For the case in which simplicity is also required, we give a triple consisting of two quasiplanar graphs and a star that does not admit a QSEFE. Moreover, in contrast to the planar SEFE problem, we show that it is not always possible to obtain a QSEFE for two matchings if the quasiplanar drawing of one matching is fixed. 

   more » « less
5. Noncrossing Longest Paths and Cycles

   https://doi.org/10.4230/LIPIcs.GD.2024.36  

   Aloupis, Greg; Biniaz, Ahmad; Bose, Prosenjit; De_Carufel, Jean-Lou; Eppstein, David; Maheshwari, Anil; Odak, Saeed; Smid, Michiel; Tóth, Csaba D; Valtr, Pavel (October 2024, Schloss Dagstuhl – Leibniz-Zentrum für Informatik)

   Felsner, Stefan; Klein, Karsten (Ed.)

   Edge crossings in geometric graphs are sometimes undesirable as they could lead to unwanted situations such as collisions in motion planning and inconsistency in VLSI layout. Short geometric structures such as shortest perfect matchings, shortest spanning trees, shortest spanning paths, and shortest spanning cycles on a given point set are inherently noncrossing. However, the longest such structures need not be noncrossing. In fact, it is intuitive to expect many edge crossings in various geometric graphs that are longest. Recently, Álvarez-Rebollar, Cravioto-Lagos, Marín, Solé-Pi, and Urrutia (Graphs and Combinatorics, 2024) constructed a set of points for which the longest perfect matching is noncrossing. They raised several challenging questions in this direction. In particular, they asked whether the longest spanning path, on any finite set of points in the plane, must have a pair of crossing edges. They also conjectured that the longest spanning cycle must have a pair of crossing edges. In this paper, we give a negative answer to the question and also refute the conjecture. We present a framework for constructing arbitrarily large point sets for which the longest perfect matchings, the longest spanning paths, and the longest spanning cycles are noncrossing. 

   more » « less