Alexander Metzger

Alexander Metzger, Austin Ulrigg

We study the problem of determining the minimal genus of a simple finite connected graph. We present an algorithm which, for an arbitrary graph $G$ with $n$ vertices and $m$ edges, determines the orientable genus of $G$ in $O(n(4^m/n)^{n/t})$ steps where $t$ is the girth of $G$. This algorithm avoids difficulties that many other genus algorithms have with handling bridge placements which is a well-known issue. The algorithm has a number of useful properties for practical use: it is simple to implement, it outputs the faces of an optimal embedding, and it iteratively narrows both upper and lower bounds. We illustrate the algorithm by determining the genus of the $(3,12)$ cage (which is 17); other graphs are also considered.

Zhihan Zhang, Alexander Metzger, Yuxuan Mei et al. · uw

Interest in sustainability information has surged in recent years. However, the data required for a life cycle assessment (LCA) that maps the materials and processes from product manufacturing to disposal into environmental impacts (EI) are often unavailable. Here we reimagine conventional LCA by introducing multimodal AI agents that emulate interactions between LCA experts and stakeholders like product managers and engineers to calculate the cradle-to-gate (production) carbon emissions of electronic devices. The AI agents iteratively generate a detailed life-cycle inventory leveraging a custom data abstraction and software tools that extract information from online text and images from repair communities and government certifications. This approach reduces weeks or months of expert time to under one minute and closes data availability gaps while yielding carbon footprint estimates within 19% of expert LCAs with zero proprietary data. Additionally, we develop a method to directly estimate EI by comparing an input to a cluster of products with similar descriptions and known carbon footprints. This runs in 3 ms on a laptop with a MAPE of 12.28% on electronic products. Further, we develop a data-driven method to generate emission factors. We use the properties of an unknown material to represent it as a weighted sum of emission factors for similar materials. Compared to human experts picking the closest LCA database entry, this improves MAPE by 120.26%. We analyze the data and compute scaling of this approach and discuss its implications for future LCA workflows.