Search

Let τ (G) and τ G (e) be the number of spanning trees of a connected graph G and the number of spanning trees of G containing edge e. The ratio d G (e) = τ G (e) / τ (G) is called the spanning tree edge density, or simply density, of e. The maximum density dep (G) = max e ∈ E (G) d G (e) is called the spanning tree edge dependence, or simply dependence, of G. In 2016, Kahl made the following two conjectures. (C1) Let p , q be positive integers, p < q. There exists some function f (p , q) such that, if G is the bipartite construction as given in Theorem 3.5 (Theorem 2.1 in the present paper), then t i ≥ f (p , q) for all 2 ≤ i ≤ n implies that dep (G) = p / q. (C2) Let p , q be positive integers, p < q. There exists a planar graph G such that dep (G) = p / q. In this paper, by using combinatorial and electrical network approaches, firstly, we show (C1) is true. Secondly, we disprove (C2) by showing that for any planar graph G , dep (G) > 1 3 . On the other hand, by construction families of planar graphs, we show that, for p / q > 1 2 , there do exist a planar graph G such that dep (G) = p / q. Furthermore, we prove that the second conjecture holds for planar multigraphs. [ABSTRACT FROM AUTHOR]

Relating image contours and regions and their attributes according to connectivity based on incidence or adjacency is a crucial task in numerous applications in the fields of image processing, computer vision and pattern recognition. In this paper, the crucial incidence topological information of 2-dimensional images is extracted in an efficient manner through the computation of a new structure called the HomDuRAG of an image; that is, the dual graph of the HomRAG (a topologically consistent extended version of the classical RAG). These representations are derived from the two traditional self-dual square grids (in which physical pixels play the role of 2-dimensional cells) and encapsulate the whole set of topological features and relations between the three types of objects embedded in a digital image: 2-dimensional (regions), 1-dimensional (contours) and 0-dimensional objects (crosses). Here, a first version of a fully parallel algorithm to compute this new representation is presented, whose timing complexity order (in the worst case and supposing one processing element per 0-cell) is O (l o g (M × N)) , M and N being the height and width of the image. Efficient implementations of this parallel algorithm would allow images to be processed in real time, as well as permit us to uncover fast algorithms for contour detection and segmentation, opening new perspectives within the image processing field. [ABSTRACT FROM AUTHOR]

Accurately assessing the resilience of the road network is crucial for responding to emergencies and enhancing public safety. Signal control plays a significant role in managing traffic flow. However, its impact is often overlooked in resilience assessments, where traffic flow and signal control are usually considered separately. A Movement-Specific Resilience (MSR) assessment model is proposed to integrate signal timing into resilience analysis. To accurately represent traffic flow paths under phase control, a dual graph is used to depict the topological network, allowing the assessment of relationships among all movements at an intersection. Based on this, a cascading failure model is developed to analyze the impact of signal control on traffic flow reassignment, reflecting how signal timing influences traffic flow propagation after failures. The method is validated using data collected from a sub-road network in Xi'an city. Results reveal the cumulative resilience of single lanes is not equivalent to the resilience of road segments. The MSR is higher when the network's failure degree is low and decreases as the failure level increases. Furthermore, road saturation is inversely related to MSR, while MSR is proportional to capacity. MSR remains unaffected by failures and oversaturation when capacity exceeds a certain threshold. These insights could be a theoretical foundation for bolstering resilience via signal control adjustments. [ABSTRACT FROM AUTHOR]

Urban street profiling is the spatio-temporal pattern discovery of street-level urban areas, which plays a vital role in understanding urban structures and dynamics. Due to the natural topology and various geographic characteristics on the streets, it is necessary to combine multi-dimensional spatio-temporal information to understand different profiles of streets. This research aims to develop a street profiling framework according to the coupled characteristics of streets. At the start, a bidirected dual graph and a spatial weighted graph embedding method were used to solve the street representation. Then, the street profiles can be extracted by clustering embedding vectors of streets and feature importance analysis. As the case study, we employed the bike trajectories and street view images in Xiamen, China to depict the geographic attributes of streets. The results can reveal nine spatio-temporal street profiles from the biking perspective, including three spatial distribution patterns and two spatial semantic patterns. Urban streets in the study area show a significant hierarchical pattern because of locations and the spatial lags of the biking behaviors. Meanwhile, the spatio-temporal characteristics of biking behaviors are the main factors of street profiles, though the street environment attributes participate in over half the number of profile types. We further evaluated the profiling ability of the proposed framework and the importance of urban street profiles using coupled characteristics. Overall, this study explored the profiling method for coupling static and dynamic characteristics of urban streets. The profiling results also help understand street usage and experiences by bikers, which have a practical value on the human-oriented classification of streets and further urban development from a geographic view. • Urban street profiling by the coupled spatio-temporal patterns and biking activities. • Bidirected dual graph was employed to couple multi-dimensional spatial attributes. • Spatial weighted GraphMAE was improved to train the embedding vectors of streets. • Nine types of urban street profiles were found with three spatial distribution. [ABSTRACT FROM AUTHOR]

The rapid development of natural language processing (NLP) technologies has enabled the emergence of legal intelligence assistance systems, with legal charge prediction (LCP) being a critical technology. The automatic LCP aims to determine the final charges based on fact descriptions of criminal cases. LCP assists human judges in managing workloads and improving efficiency, provides accessible legal guidance for individuals, and supports enterprises in litigation financing and compliance monitoring. However, distinguishing between confusing charges in real-world judicial practice remains a significant challenge. Most exist works cannot effectively capture complex relationships and discern subtle differences in fact descriptions while ignoring the legal schematic knowledge. In order to improve confusing LCP performance, we propose a novel knowledge-aware model for legal charge prediction that leverages Graph Neural Networks (GNNs) to capture complex relationships within criminal case descriptions. Specifically, the model constructs structural and semantic graphs from fact descriptions and integrates information from both through a dual-graph interaction process. A legal knowledge transformer generates key knowledge representations at schema and charge levels, while a knowledge matching network incorporates hierarchical charge knowledge into facts. Besides, we also propose two real-world datasets namely Criminal-All and Criminal-Confusing, containing 203 different charges and 86 confusing charges, respectively. To the best of our knowledge, these datasets are the first well-organized datasets for confusing LCP task. Experimental results demonstrate that the proposed model outperforms baselines and significantly improves the distinction of confusing charges, providing valuable support for intelligent legal judgment systems. • A legal schematic knowledge-aware model for confusing charges. • Dual-graph interaction to integrate information from structural and semantic graphs. • A hierarchical transformer to obtain legal knowledge representations. • A deep matching network for incorporating domain knowledge into the fact. • Our model improvement outperforms baselines and achieves a significant. [ABSTRACT FROM AUTHOR]

We find all polyhedral graphs such that their complements are still polyhedral. These turn out to be all self-complementary. [ABSTRACT FROM AUTHOR]

The dual of a polyhedron is a polyhedron—or in graph‐theoretical terms: the dual of a 3‐connected plane graph is a 3‐connected plane graph. Astonishingly, except for sufficiently large facewidth, not much is known about the connectivity of the dual on higher surfaces. Are the duals of 3‐connected embedded graphs of higher genus 3‐connected, too? If not, which connectivity guarantees 3‐connectedness of the dual? In this article, we give answers to some of these and related questions. We prove that there is no connectivity that guarantees the 3‐connectedness or 2‐connectedness of the dual for every genus, and give upper bounds for the minimum genus for which (with c>2 $c\gt 2$) a c‐connected embedded graph with a dual that has a 1‐ or 2‐cut can occur. We prove that already on the torus, we need 6‐connectedness to guarantee 3‐connectedness of the dual and 4‐connectedness to guarantee 2‐connectedness of the dual. In the last section, we answer a related question by Plummer and Zha on orientable embeddings of highly connected noncomplete graphs. [ABSTRACT FROM AUTHOR]

Graph theory is one of the neglected branches of mathematics in Nigeria but with the most applications in other fields of research. This article shows the paucity, importance, and necessity of graph theory in the development of Nigeria. The adjacency matrix and dual graph of the Nigeria map were presented. The graph spectrum and energies (graph energy and Laplacian energy) of the dual graph were computed. Then the chromatic number, maximum degree, minimum spanning tree, graph radius, and diameter, the Eulerian circuit and Hamiltonian paths from the dual graph were obtained and discussed. [ABSTRACT FROM AUTHOR]

Let G be a plane graph with a set of faces F (G) and ψ : V (G) → { 1 , 2 , ... , k } be a (not necessarily proper) vertex k -coloring. ψ is called polychromatic if all k colors appear on the vertices of its boundary for each face (also the outer-face) f ∈ F (G). The polychromatic number of G is the largest number of colors k such that G admits a polychromatic k -coloring. In the paper, we consider a class of plane graphs with minimum face size g , in each of which every pair of faces have at most t common incident vertices, and show that the polychromatic number for each G ∈ is at least g − t − 2. When g ≥ 4 t + 4 , the result improves a known lower bound. [ABSTRACT FROM AUTHOR]

Distance-hereditary graphs can be characterized by every cycle of length at least 5 having crossing chords. This makes distance-hereditary graphs susceptible to dualizing, using the common extension of geometric face/vertex planar graph duality to cycle/cutset duality as in abstract matroidal duality. The resulting "DH* graphs" are characterized and then analyzed in terms of connectivity. These results are used in a special case of plane-embedded graphs to justify viewing DH* graphs as the duals of distance-hereditary graphs. [ABSTRACT FROM AUTHOR]

After Curl, Kroto and Smalley were awarded 1996 the Nobel Prize in chemistry, fullerenes have been subject of much research. One part of that research is the prediction of a fullerene's stability using topological descriptors. It was mainly done by considering the distribution of the twelve pentagonal facets on its surface, calculations mostly were performed on all isomers of C40, C60 and C80. This paper suggests a novel method for the classification of combinatorial fullerene isomers using spectral graph theory. The classification presupposes an invariant scheme for the facets based on the Schlegel diagram. The main idea is to find clusters of isomers by analyzing their graph structure of hexagonal facets only. We also show that our classification scheme can serve as a formal stability criterion, which became evident from a comparison of our results with recent quantum chemical calculations (Sure et al. in Phys Chem Chem Phys 19:14296–14305, 2017). We apply our method to classify all isomers of C60 and give an example of two different cospectral isomers of C44. Calculations are done with our own Python scripts available at (Bille et al. in Fullerene database and classification software, https://www.uni-ulm.de/mawi/mawi-stochastik/forschung/fullerene-database/, 2020). The only input for our algorithm is the vector of positions of pentagons in the facet spiral. These vectors and Schlegel diagrams are generated with the software package Fullerene (Schwerdtfeger et al. in J Comput Chem 34:1508–1526, 2013). [ABSTRACT FROM AUTHOR]

Motivated in part by Propp's intruded Aztec diamond regions, we consider hexagonal regions out of which two horizontal chains of triangular holes (called ferns) are removed, so that the chains are at the same height, and are attached to the boundary. By contrast with the intruded Aztec diamonds (whose numbers of domino tilings contain some large prime factors in their factorization), the number of lozenge tilings of our doubly-intruded hexagons turns out to be given by simple product formulas in which all factors are linear in the parameters. We present in fact q -versions of these formulas, which enumerate the corresponding plane-partitions-like structures by their volume. We also pose some natural statistical mechanics questions suggested by our set-up, which should be possible to tackle using our formulas. [ABSTRACT FROM AUTHOR]

We compare one-dimensional representations for the isotopy stable dynamics of homeomorphisms in two dimensions. We consider the skeleton graph representative, which captures periodic behaviour, and the homotopy graph representative which captures homo-/heteroclinic behaviour. The main result of this paper is to show that the dual to the skeleton graph representative is the homotopy graph representative of the inverse map. This gives a strong link between different methods for computing the dynamics. [ABSTRACT FROM AUTHOR]

Given an algebraic variety X defined over an algebraically closed field, we study the space RZ(X, x) consisting of all the valuations of the function field of X which are centered in a closed point x of X. We concentrate on its homeomorphism type. We prove that, when x is a regular point, this homeomorphism type only depends on the dimension of X. If x is a singular point of a normal surface, we show that it only depends on the dual graph of a good resolution of (X, x) up to some precise equivalence. This is done by studying the relation between RZ(X, x) and the normalized non-Archimedean link of x in X coming from the point of view of Berkovich geometry. We prove that their behavior is the same. [ABSTRACT FROM AUTHOR]

Abstract In their paper about a dual of MacMahon's classical theorem on plane partitions, Ciucu and Krattenthaler proved a closed form product formula for the tiling number of a hexagon with a "shamrock", a union of four adjacent triangles, removed in the center (Ciucu and Krattenthaler, 2013). Lai later presented a q -enumeration for lozenge tilings of a hexagon with a shamrock removed from the boundary (Lai, 2017). It appears that the above are the only two positions of the shamrock hole that yield nice tiling enumerations. In this paper, we show that in the case of symmetric hexagons, we always have a simple product formula for the number of tilings when removing a shamrock at any position along the symmetry axis. Our result also generalizes Eisenkölbl's related work about lozenge tilings of a hexagon with two unit triangles missing on the symmetry axis (Eisenkölbl, 1999). [ABSTRACT FROM AUTHOR]

Abstract Kenyon and Wilson showed how to test if a circular planar electrical network with n nodes is well-connected by checking the positivity of ( n 2 ) central minors of the response matrix. Their test is based on the fact that any contiguous minor of a matrix can be expressed as a Laurent polynomial in the central minors. Moreover, the Laurent polynomial is the generating function of domino tilings of a weighted Aztec diamond. They conjectured that a larger family of minors, semicontiguous minors, can also be written in terms of domino tilings of a region on the square lattice. In this paper, we present a proof of the conjecture. [ABSTRACT FROM AUTHOR]

• We enumerate spanning trees with a Kekule structure in the linear hexagonal chains on the plane. • We enumerate spanning trees with a Kekule structure in the linear hexagonal chains on the cylinder. • We enumerate spanning trees with a Kekule structure in the linear hexagonal chains on the Mobius strip. In chemical graph theory, many topological indices of the hexagonal chains, for instance, the energy, Wiener and Kirchhoff indices, and numbers of Kekulé structures and spanning trees, and so on, have been studied extensively. We enumerate spanning trees with a Kekulé structure in the linear hexagonal chains on the plane, cylinder and Möbius strip, respectively. [ABSTRACT FROM AUTHOR]

Abstract We begin the study of the notion of diameter of an ideal I ⊂ S = k [ x 1 , ... , x n ] , an invariant measuring the distance between the minimal primes of I. We provide large classes of Hirsch ideals, i.e. ideals satisfying diam (I) ≤ height (I) , such as: quadratic radical ideals such that S / I is Gorenstein and height (I) ≤ 4 , or ideals admitting a square-free complete intersection initial ideal. [ABSTRACT FROM AUTHOR]

A rectangular floor plan (RFP) is a floor plan in which plan's boundary and each room is a rectangle. The problem is to construct a RFP for the given adjacency requirements, if it exists. In this paper, we aim to present a generic solution to the above problem by enumerating a set of RFP that topologically contain all possible RFP. This set of RFP is called generic rectangular floor plans (GRFP). Furthermore, the construction of GRFP leads us to the necessary condition for the existence of a RFP corresponding to a given graph. [ABSTRACT FROM AUTHOR]

A parallel algorithm is proposed for scalable generation of large-scale tetrahedral meshes. The key innovation is the use of a mesh-simplification based domain decomposition approach. This approach works on a background mesh with both its surface and its interior elements much larger than the final elements desired, and decomposes the domain into subdomains containing no undesirable geometric features in the inter-domain interfaces. In this way, the most time-consuming part of domain decomposition can be efficiently parallelized, and other sequential parts consume reasonably limited computing time since they treat a very coarse background mesh. Meanwhile, the subsequent parallel procedures of mesh generation and improvement are most efficient because they can treat individual subdomains without compromising element quality. Compared with published state-of-the-art parallel algorithms, the developed parallel algorithm can reduce the clock time required by the creation of one billion elements on 512 computer cores from roughly half an hour to less than 4 minutes. [ABSTRACT FROM AUTHOR]

Summary: Fluid‐driven fractures of brittle rock is simulated via a dual‐graph lattice model. The new discrete hydromechanical model incorporates a two‐way coupling mechanism between the discrete element model and the flow network. By adopting an operator‐split algorithm, the coupling model is able to replicate the transient poroelasticity coupling mechanism and the resultant Mandel‐Cryer hydromechanical coupling effect in a discrete mechanics framework. As crack propagation, coalescence and branching are all path‐dependent and irreversible processes, capturing this transient coupling effect is important for capturing the essence of the fluid‐driven fracture in simulations. Injection simulations indicate that the onset and propagation of fractures is highly sensitive to the ratio between the injection rate and the effective permeability. Furthermore, we show that in a permeable rock, the borehole breakdown pressure, the pressure at which fractures start to grow from the borehole, depends on both the given ratio between injection rate and permeability and the Biot coefficient. [ABSTRACT FROM AUTHOR]

Let P be a simple polygon with n vertices. The dual graph T ⁎ of a triangulation T of P is the graph whose vertices correspond to the bounded faces of T and whose edges connect those faces of T that share an edge. We consider triangulations of P that minimize or maximize the diameter of their dual graph. We show that both triangulations can be constructed in O ( n 3 log ⁡ n ) time using dynamic programming. If P is convex, we show that any minimizing triangulation has dual diameter exactly 2 ⋅ ⌈ log 2 ⁡ ( n / 3 ) ⌉ or 2 ⋅ ⌈ log 2 ⁡ ( n / 3 ) ⌉ − 1 , depending on n . Trivially, in this case any maximizing triangulation has dual diameter n − 2 . Furthermore, we investigate the relationship between the dual diameter and the number of ears (triangles with exactly two edges incident to the boundary of P ) in a triangulation. For convex P , we show that there is always a triangulation that simultaneously minimizes the dual diameter and maximizes the number of ears. In contrast, we give examples of general simple polygons where every triangulation that maximizes the number of ears has dual diameter that is quadratic in the minimum possible value. We also consider the case of point sets in general position in the plane. We show that for any such set of n points there are triangulations with dual diameter in O ( log ⁡ n ) and in Ω ( n ) . [ABSTRACT FROM AUTHOR]

Proctor's work on staircase plane partitions yields an enumeration of lozenge tilings of a halved hexagon on the triangular lattice. Rohatgi recently extended this tiling enumeration to a halved hexagon with a triangle removed from the boundary. In this paper, we prove a generalization of the results of Proctor and Rohatgi by enumerating lozenge tilings of a halved hexagon in which an array of an arbitrary number of adjacent triangles has been removed from the boundary. [ABSTRACT FROM AUTHOR]

We define an algebraic analogue, in the case of jacobians of curves, of the height jump divisor introduced recently by R. Hain. We give explicit combinatorial formulae for the height jump for families of semistable curves using labelled reduction graphs. With these techniques we prove a conjecture of Hain on the effectivity of the height jump, and also give a new proof of a theorem of Tate, Silverman and Green on the variation of heights in families of abelian varieties. [ABSTRACT FROM AUTHOR]

Presently, a tetrahedral mesher based on the Delaunay triangulation approach may outperform a tetrahedral improver based on local smoothing and flip operations by nearly one order in terms of computing time. Parallelization is a feasible way to speed up the improver and enable it to handle large-scale meshes. In this study, a novel domain decomposition approach is proposed for parallel mesh improvement. It analyses the dual graph of the input mesh to build an inter-domain boundary that avoids small dihedral angles and poorly shaped faces. Consequently, the parallel improver can fit this boundary without compromising the mesh quality. Meanwhile, the new method does not involve any inter-processor communications and therefore runs very efficiently. A parallel pre-processing pipeline that combines the proposed improver and existing parallel surface and volume meshers can prepare a quality mesh containing hundreds of millions of elements in minutes. Experiments are presented to show that the developed system is robust and applicable to models of a complication level experienced in industry. [ABSTRACT FROM AUTHOR]

An under-explored topic within the field of planning and housing studies is related to the definition of local area unit. An empirical problem that arises is that different types of local area units can infer different results. This could be in constructing segregation indices, in estimating hedonic price models or in identifying housing submarkets. This research proposes the concept of Street-based Local Area (SLA), in asking to what extent SLA associate with house price. In order to examine this question, this article borrows from network science and space syntax research in defining SLA. This research conjectures that SLA has a significant effect on house price and that this effect is captured more strongly than ad-hoc administrative region-based local area. In order to test this conjecture, this research adopted the multi-level hedonic price approach to estimate local area effects on house prices for the case study of Metropolitan London in the United Kingdom. Results showed significant local area effects on house prices and that SLA is preferred to region-based one. The plausible reasons are firstly, people perceived the local area on a street network. Street-based Local Area is able to capture more precisely subtle perceptual differences in an urban environment than an ad-hoc administrative region. Second, the topology of the street network reinforces the socio-economic similarity/differences overtime. Differences between local areas can become more pronounced as like-minded people bump into each other, cluster together and share information with each other. Third, as people identify these local areas they would make decisions based on it. The local area becomes part of the housing bundle leading to it having an effect on house price. The main contribution of the research is the novel application of community detection techniques on the street-network dual graph to defining SLA. This is important as it links the topology of the street network to how we define and perceive local area and it presents an alternative to ad-hoc administrative geographies that are currently applied in many aspects of neighbourhood planning. [ABSTRACT FROM AUTHOR]

Knowledge graph (KG) is a kind of structured human knowledge of modeling the relations between real-world entities. This paper studies the KG inductive inference problem, i.e., predicting the relations for out-of-KG entities. However, due to the incomplete nature of the KGs, the connections of some relations are missing. This makes existing differentiable rule learning methods unable to represent some possible rule candidates, which will further affect the inductive inference result. To solve this challenge, our research hypothesis is that the semantics of relation's argument can be well used to reflect the possible connections between relations. We propose a KG inductive inference model, RuleNet, which consists of two parts. Firstly, a query-dependent dual graph construction method is proposed, which is able to learn the relation connections using the information of the relation's argument. Secondly, a dual graph traversing method is proposed, which is able to traverse all possible rule candidates even if some rules cannot be formed due to the missing edges. Performance of the proposed methods is evaluated using the FB15K237 (10%–20%), WN18RR (10%–20%) and YAGO3-10 (10%–20%) benchmarks. Experimental results show that RuleNet achieves a superior performance compared with many strong baselines. Ablation studies have verified the effectiveness of the proposed network components. Qualitative analysis shows that RuleNet can learn meaningful dual graph and logic rules. • A rule-inductive model is proposed to solve the KG inductive inference problem. • The semantic information of relation's argument is used to construct a dual graph. • A dual graph traversing method is proposed to learn all possible rule candidates. • The model can significantly improve the performance of KG inductive inference. [ABSTRACT FROM AUTHOR]

We consider a generating function of the domino tilings of an Aztec rectangle with several unit squares removed from the boundary. Our generating function involves two statistics: the rank of the tiling and half number of vertical dominoes as in the Aztec diamond theorem by Elkies, Kuperberg, Larsen and Propp. In addition, our work deduces a combinatorial explanation for an interesting connection between the number of lozenge tilings of a semihexagon and the number of domino tilings of an Aztec rectangle. [ABSTRACT FROM AUTHOR]

The author gave a proof of a generalization of the Aztec diamond theorem for a family of 4-vertex regions on the square lattice with southwest-to-northeast diagonals drawn in Lai (2014) by using a bijection between tilings and non-intersecting lattice paths. In this paper, we use Kuo graphical condensation to give a new proof. [ABSTRACT FROM AUTHOR]

In this paper, we deal with the enumeration of spanning trees in planar graphs using some combinatorial structures such as duality, bipartition and reduction. It is well known that the number of spanning trees in a planar graph is equal to the one in its dual. Based on this result, our contribution is to propose a formula that state the relation between the number of spanning trees in a given graph and in its bipartite. Then, similarly we establish a formula for the reduced graph. Finally, we extend the results of the deletion, the contraction and the splitting techniques to investigate the complexity in these combinatorial structures. The main advantage of our proposal is to derive spanning trees recursions in order to over- come the hardiness of computing the complexity of a given planar graph using the existing methods. [ABSTRACT FROM AUTHOR]

If X is a geodesic metric space and $$x_1,x_2,x_3$$ are three points in $$X$$ , a geodesic triangle $$T=\{x_1,x_2,x_3\}$$ is the union of three geodesics $$[x_1x_2]$$ , $$[x_2x_3]$$ and $$[x_3x_1]$$ in $$X$$ . The space $$X$$ is $$\delta $$ - hyperbolic $$($$ in the Gromov sense $$)$$ if any side of $$T$$ is contained in a $$\delta $$ -neighborhood of the union of the two other sides, for every geodesic triangle $$T$$ in $$X$$ . The study of hyperbolic graphs is an interesting topic since the hyperbolicity of a geodesic metric space is equivalent to the hyperbolicity of a graph related to it. In this paper we obtain criteria which allow us to decide, for a large class of graphs, whether they are hyperbolic or not. We are especially interested in the planar graphs which are the 'boundary' (the $$1$$ -skeleton) of a tessellation of the Euclidean plane. Furthermore, we prove that a graph obtained as the $$1$$ -skeleton of a general CW $$2$$ -complex is hyperbolic if and only if its dual graph is hyperbolic. [ABSTRACT FROM AUTHOR]

Distribution systems are most commonly operated in a radial configuration for a number of reasons. In order to impose radiality constraint in the optimal network reconfiguration problem, an efficient algorithm is introduced in this paper based on graph theory. The paper shows that the normally followed methods of imposing radiality constraint within a mixed-integer programming formulation of the reconfiguration problem may not be sufficient. The minimum-loss network reconfiguration problem is formulated using different ways to impose radiality constraint. It is shown, through simulations, that the formulated problem using the proposed method for representing radiality constraint can be solved more efficiently, as opposed to the previously proposed formulations. This results in up to 30% reduction in CPU time for the test systems used in this study. [ABSTRACT FROM AUTHOR]

We characterize, in terms of its idempotents, the Leavitt path algebras of an arbitrary graph that satisfies Condition (L) or Condition (NE). In the latter case, we also provide the structure of such algebras. Dual graph techniques are considered and demonstrated to be useful in the approach of the study of Leavitt path algebras of arbitrary graphs. A refining of the so-called Reduction Theorem is achieved and is used to prove that I( Pc( E)), the ideal of the vertices which are base of cycles without exits of the graph E, a construction with a clear parallelism to the socle, is a ring isomorphism invariant for arbitrary Leavitt path algebras. We also determine its structure in any case. [ABSTRACT FROM AUTHOR]

Bounding Volume Hierarchies (BVHs) are essential tools in performing collision detection on three-dimensional information. They reduce the number of expensive calculations required to determine whether or not two geometrical entities collide by using inexpensive calculations to rule out parts of the objects that could not possibly intersect. Quickly producing a high quality BVH is an important aspect of three-dimensional multimedia analysis. As such a powerful optimization, efficient and high quality BVHs are still an active area of research. Herein, the authors present a novel BVH representation that reduces the redundancy in the tree structure by allowing a node to contain an arbitrary number of children, as well as compressing non-unique nodes and combining their children. A new partitioning scheme using a graphical representation of the object is also presented to improve the quality of the generated BVH. [ABSTRACT FROM AUTHOR]

The automatic generalization of urban street networks is a constant and important aspect of geographical information science. Previous studies show that the dual graph for street-street relationships more accurately reflects the overall morphological properties and importance of streets than do other methods. In this study, we construct a dual graph to represent street-street relationship and propose an approach to generalize street networks based on gravitational field theory. We retain the global structural properties and topological connectivity of an original street network and borrow from gravitational field theory to define the gravitational force between nodes. The concept of multi-order neighbors is introduced and the gravitational force is taken as the measure of the importance contribution between nodes. The importance of a node is defined as the result of the interaction between a given node and its multi-order neighbors. Degree distribution is used to evaluate the level of maintaining the global structure and topological characteristics of a street network and to illustrate the efficiency of the suggested method. Experimental results indicate that the proposed approach can be used in generalizing street networks and retaining their density characteristics, connectivity and global structure. [ABSTRACT FROM AUTHOR]

Abstract: Matt Blum conjectured that the number of tilings of the hexagonal dungeon of sides a, 2a, b, a, 2a, b (where ) is (Propp, 1999 [4]). In this paper we present a proof for this conjecture using Kuo's Graphical Condensation Theorem (Kuo, 2004 [2]). [Copyright &y& Elsevier]

Abstract: In a recent paper Dubrovin et al. (1998), it is proved that the genus two free energy of an arbitrary semisimple Frobenius manifold can be represented as a sum of contributions associated with dual graphs of certain stable algebraic curves of genus two plus the so called genus two -function, and for a certain class of Frobenius manifolds it is conjectured that the associated genus two -functions vanish. In this paper, we prove this conjecture for the Frobenius manifolds associated with simple singularities of type A. [Copyright &y& Elsevier]

In this article, we establish a connection between two models for r -spin structures on surfaces: the marked PLCW decompositions of Novak and Runkel-Szegedy, and the structured graphs of Dyckerhoff-Kapranov. We use these models to describe r -spin structures on open-closed bordisms, leading to a generators-and-relations characterization of the 2-dimensional open-closed r -spin bordism category. This results in a classification of 2-dimensional open closed field theories in terms of algebraic structures we term "knowledgeable Λ r -Frobenius algebras". We additionally extend the state sum construction of closed r -spin TFTs from a Λ r -Frobenius algebra A with invertible window element of Novak and Runkel-Szegedy to the open-closed case. The corresponding knowledgeable Λ r -Frobenius algebra is A together with the Z / r -graded center of A. [ABSTRACT FROM AUTHOR]

Abstract: We present a class of graphs whose adjacency matrices are nonsingular with integral inverses, denoted h-graphs. If the h-graphs G and H with adjacency matrices and satisfy , where S is a signature matrix, we refer to H as the dual of G. The dual is a type of graph inverse. If the h-graph G is isomorphic to its dual via a particular isomorphism, we refer to G as strongly self-dual. We investigate the structural and spectral properties of strongly self-dual graphs, with a particular emphasis on identifying when such a graph has 1 as an eigenvalue. [Copyright &y& Elsevier]

We study the Torelli morphism from the moduli space of stable curves to the moduli space of principally polarized stable semi-abelic pairs. We give two characterization of its fibers. describe its injectivity locus, and give a sharp upper bound on the cardinality of finite fibers. We also bound the dimension of infinite fibers. [ABSTRACT FROM AUTHOR]

Abstract: The centrality and efficiency measures of a network are strongly related to the respective measures on the dual and the bipartite associated networks. We show some relationships between the Bonacich centralities , and and between the efficiencies and and we compute the behavior of these parameters in some examples. [ABSTRACT FROM AUTHOR]

face of a vertex coloured plane graph is called loose if the number of colours used on its vertices is at least three. The looseness of a plane graph G is the minimum k such that any surjective k-colouring involves a loose face. In this paper we prove that the looseness of a connected plane graph G equals the maximum number of vertex disjoint cycles in the dual graph G* increased by 2. We also show upper bounds on the looseness of graphs based on the number of vertices, the edge connectivity, and the girth of the dual graphs. These bounds improve the result of Negami for the looseness of plane triangulations. We also present infinite classes of graphs where the equalities are attained. [ABSTRACT FROM AUTHOR]

Abstract: The main purpose of the paper is to develop an approach to the evaluation or the estimation of the spanning tree congestion of planar graphs. This approach is used to evaluate the spanning tree congestion of triangular grids. [Copyright &y& Elsevier]

The exceptional divisor component of the projective plane modified by a sequence of blow-ups determines filtration on the ring of polynomials in two variables. The set of such components determines the multi-index filtration on this ring. The Poincaré series of this filtration is calculated for some sets of components provided that the modification under study is the minimal resolution of a plane algebraic curve with one place at infinity. [ABSTRACT FROM AUTHOR]

The Jordan Curve Theorem referring to a simple closed curve in the plane has a particularly simple proof in the case that the curve is polygonal, called the “raindrop proof”. We generalize the notion of a simple closed polygon to that of a polyhedral ( d−1)-pseudomanifold ( d≥2) and prove a Jordan–Brouwer Separation Theorem for such a manifold embedded in ℝ d. As a by-product, we get bounds on the polygonal diameter of the interior and exterior of such a manifold which are almost tight. This puts the result within the frame of computational geometry. [ABSTRACT FROM AUTHOR]

Abstract: We present a class of graphs whose adjacency matrices are nonsingular with integral inverses, denoted h-graphs. For the h-graph with adjacency matrix , we consider the problem of identifying exactly when is signature-similar to the adjacency matrix of another h-graph, . When this holds, is a type of graph-inverse of , which is known as the dual of . We present necessary and sufficient conditions for the existence of . As an application, we provide a characterization of all dual pairs and where both graphs are unicyclic. This characterization allows us to identify those h-graphs that are unicyclic and self-dual. [Copyright &y& Elsevier]

Abstract: We propose a traffic simulation model for urban system based on the dual graph representation of a urban road network and with a random entering vehicle rate. To avoid the shortcoming of “Space Syntax” of ignoring the road''s metric distance, we consider both the motion of the vehicles along roads and the navigation of the vehicles in the network. Simulations have shown some basic properties of urban traffic system, such as flux fluctuation, crisis and dissipation, phase transition from a free flow to jams, overall capacity, the distribution of traveling time, and the fundamental diagram. The system''s behavior greatly depends on the topology of the transportation network. A well-planned lattice grid can keep more vehicles travelling. The critical entering vehicle rate is much greater in lattice grid than in a self-organized network. The vehicles have to travel longer time in a self-organized urban system due to the navigation cost. [Copyright &y& Elsevier]

Whereas many viruses have capsids of uniquely defined sizes that observe icosahedral symmetry, retrovirus capsids are highly polymorphic. Nevertheless, they may also be described as polyhedral foldings of a fullerene lattice on which the capsid protein (CA) is arrayed. Lacking the high order of symmetry that facilitates the reconstruction of icosahedral capsids from cryo-electron micrographs, the 3D structures of individual retrovirus capsids may be determined by cryo-electron tomography, albeit at lower resolution. Here, we describe computational and graphical methods used to construct polyhedral models that match in size and shape, capsids of Rous sarcoma virus (RSV) observed within intact virions. The capsids fall into several shape classes, including tubes, 'lozenges' and 'coffins'. The extent to which a capsid departs from icosahedral symmetry reflects the irregularity of the distribution of pentamers, which are always 12 in number for a closed polyhedral capsid. The number of geometrically distinct polyhedra grows rapidly with increasing quotas of hexamers, and ranks in the millions for particles in the size range of RSV capsids, which typically have 150-300 hexamers. Unlike the CAs of icosahedral viruses that assume a minimal number of quasi-equivalent conformations equal to the triangulation number (T), retroviral CAs exhibit a near-continuum of quasi-equivalent conformations - a property that may be attributed to the flexible hinge linking the N- and C-terminal domains. [ABSTRACT FROM AUTHOR]

We discuss the question of recurrence for persistent, or Newtonian, random walks in ℤ2, i.e. random walks whose transition probabilities depend both on the walker's position and incoming direction. We use results by Tóth and Schmidt–Conze to prove recurrence for a large class of such processes, including all "invertible" walks in elliptic random environments. Furthermore, rewriting our Newtonian walks as ordinary random walks in a suitable graph, we gain a better idea of the geometric features of the problem, and obtain further examples of recurrence. [ABSTRACT FROM AUTHOR]