keyword
planar graphs
A planar graph is a graph that can be drawn on a two-dimensional plane in such a way that its edges intersect only at their endpoints, meaning no edges cross one another. When such a graph is drawn without edge crossings, it is referred to as a plane graph or planar embedding, which divides the plane into regions called faces. Connected planar graphs satisfy Eulers formula, which states that the number of vertices minus the number of edges plus the number of faces equals two. Fundamental characterizations, such as Kuratowskis theorem and Wagners theorem, establish that a finite graph is planar if and only if it does not contain a subdivision or minor isomorphic to the complete graph on five vertices or the complete bipartite graph on six vertices divided into two sets of three. Planar graphs are central to graph theory, network design, geographic mapping, and circuit layout, and they are notably characterized by the four color theorem, which proves that the vertices of any planar graph can be colored with at most four colors such that no adjacent vertices share the same color.
4 items
Graph Generation with Diffusion Mixture
Jaehyeong Jo, Dongki Kim, Sung Ju Hwang
Why you should read this
Presents GruM, a graph generative framework that formulates the generation process as a mixture of endpoint-conditioned Ornstein-Uhlenbeck bridge diffusions to directly predict final graph topologies rather than denoise step-by-step, achieving faster convergence and superior generation across general graph and 2D/3D molecule benchmarks.
Generation of graphs is a major challenge for real-world tasks that require understanding the complex nature of their non-Euclidean structures. Although diffusion models have achieved notable success in graph generation recently, they are ill-suited for modeling the topological properties of graphs since learning to denoise the noisy samples does not explicitly learn the graph structures to be generated. To tackle this limitation, we propose a generative framework that models the topology of graphs by explicitly learning the final graph structures of the diffusion process. Specifically, we design the generative process as a mixture of endpoint-conditioned diffusion processes which is driven toward the predicted graph that results in rapid convergence. We further introduce a simple parameterization of the mixture process and develop an objective for learning the final graph structure, which enables maximum likelihood training. Through extensive experimental validation on general graph and 2D/3D molecule generation tasks, we show that our method outperforms previous generative models, generating graphs with correct topology with both continuous (e.g. 3D coordinates) and discrete (e.g. atom types) features. Our code is available at https://github.com/harryjo97/GruM.
Added
2026-10-04
Where the Really Hard Problems Are
P. Cheeseman, B. Kanefsky, W. Taylor
Why you should read this
Reveals that computationally hard instances of NP-complete problems concentrate along a phase transition boundary between underconstrained and overconstrained regions, providing an order-parameter framework to predict search difficulty and distinguish hard instances from typically easy ones.
It is well known that for many NP-complete problems, such as K-Sat, etc., typical cases are easy to solve; so that computationally hard cases must be rare (assuming P = NP). This paper shows that NP-complete problems can be summarized by at least one "order parameter", and that the hard problems occur at a critical value of such a parameter. This critical value separates two regions of characteristically different properties. For example, for K-colorability, the critical value separates overconstrained from underconstrained random graphs, and it marks the value at which the probability of a solution changes abruptly from near 0 to near 1. It is the high density of well-separated almost solutions (local minima) at this boundary that cause search algorithms to "thrash". This boundary is a type of phase transition and we show that it is preserved under mappings between problems. We show that for some P problems either there is no phase transition or it occurs for bounded N (and so bounds the cost). These results suggest a way of deciding if a problem is in P or NP and why they are different. In this paper we show that for many NP problems one or more "order parameters" can be defined, and hard instances occur around particular critical values of these order parameters. In addition, such critical values form a boundary that separates the space of problems into two regions. One region is underconstrained, so the density of solutions is high, thus making it relatively easy to find a solution. The other region is overconstrained and very unlikely to contain a solution. If there are solutions in this overconstrained region, then they have such deep local minimum (strong basin of attraction) that any reasonable algorithm is likely to find it. If there is no solution, then a backtrack search can usually establish this with ease, since potential solution paths are usually cut off early in the search. Really hard problems occur on the boundary between these two regions, where the probability of a solution is low but non-negligible. At this point there are typically many local minima corresponding to almost solutions separated by high "energy barriers". These almost solutions form deep local minima that may often trap search methods that rely on local information. Because it is possible to locate a region where hard problems occur, it is possible to predict whether a particular problem is likely to be easy to solve. We expect that in future computer scientists will produce "phase diagrams" for particular problem domains to aid in hard problem identification and for prediction of solution existence probability, such as shown in [6]. We present these ideas by first showing how phase transitions arise in problem solving, and then illustrating particular transitions through several examples with different properties.
Added
2026-09-25
OSMnx: New methods for acquiring, constructing, analyzing, and visualizing complex street networks
Geoff Boeing
Why you should read this
Introduces OSMnx, a Python package that automates the extraction, topological correction, and multi-scale spatial analysis of complex street networks directly from OpenStreetMap data.
Urban scholars have studied street networks in various ways, but there are data availability and consistency limitations to the current urban planning/street network analysis literature. To address these challenges, this article presents OSMnx, a new tool to make the collection of data and creation and analysis of street networks simple, consistent, automatable and sound from the perspectives of graph theory, transportation, and urban design. OSMnx contributes five significant capabilities for researchers and practitioners: first, the automated downloading of political boundaries and building footprints; second, the tailored and automated downloading and constructing of street network data from OpenStreetMap; third, the algorithmic correction of network topology; fourth, the ability to save street networks to disk as shapefiles, GraphML, or SVG files; and fifth, the ability to analyze street networks, including calculating routes, projecting and visualizing networks, and calculating metric and topological measures. These measures include those common in urban design and transportation studies, as well as advanced measures of the structure and topology of the network. Finally, this article presents a simple case study using OSMnx to construct and analyze street networks in Portland, Oregon.
Added
2026-09-24
Mathematics for Computer Science
Eric Lehman, F Thomson Leighton, Albert R Meyer
Why you should read this
Provides foundational mathematical tools and logical reasoning skills necessary for solving complex problems in computer science.
This book provides a comprehensive introduction to mathematics for computer science, covering fundamental topics such as proofs, the well-ordering principle, logical formulas, and mathematical data types including sets, sequences, functions, and binary relations.
Added
2026-08-18
