Search

Recent advancements in Large Language Models (LLMs) like ChatGPT and GPT-4 have shown remarkable abilities in a wide range of tasks such as summarizing texts and assisting in coding. Scientific research has demonstrated that these models can also play text-adventure games. This study aims to explore whether LLMs can autonomously create text-based games based on anthropological classics, evaluating also their effectiveness in communicating knowledge. To achieve this, the study engaged anthropologists in discussions to gather their expectations and design inputs for an anthropologically themed game. Through iterative processes following the established HCI principle of 'design thinking', the prompts and the conceptual framework for crafting these games were refined. Leveraging GPT3.5, the study created three prototypes of games centered around the seminal anthropological work of the social anthropologist's Bronislaw Malinowski's "Argonauts of the Western Pacific" (1922). Subsequently, evaluations were conducted by inviting senior anthropologists to playtest these games, and based on their inputs, the game designs were refined. The tests revealed promising outcomes but also highlighted key challenges: the models encountered difficulties in providing in-depth thematic understandings, showed suspectibility to misinformation, tended towards monotonic responses after an extended period of play, and struggled to offer detailed biographical information. Despite these limitations, the study's findings open up new research avenues at the crossroads of artificial intelligence, machine learning, LLMs, ethnography, anthropology and human-computer interaction., Comment: Accepted at KUI 2024

We study the impact of forbidding short cycles to the edge density of $k$-planar graphs; a $k$-planar graph is one that can be drawn in the plane with at most $k$ crossings per edge. Specifically, we consider three settings, according to which the forbidden substructures are $3$-cycles, $4$-cycles or both of them (i.e., girth $\ge 5$). For all three settings and all $k\in\{1,2,3\}$, we present lower and upper bounds on the maximum number of edges in any $k$-planar graph on $n$ vertices. Our bounds are of the form $c\,n$, for some explicit constant $c$ that depends on $k$ and on the setting. For general $k \geq 4$ our bounds are of the form $c\sqrt{k}n$, for some explicit constant $c$. These results are obtained by leveraging different techniques, such as the discharging method, the recently introduced density formula for non-planar graphs, and new upper bounds for the crossing number of $2$-- and $3$-planar graphs in combination with corresponding lower bounds based on the Crossing Lemma., Comment: Appears in the Proceedings of the 32nd International Symposium on Graph Drawing and Network Visualization (GD 2024)

We show that every planar graph has a monotone topological 2-page book embedding where at most (4n-10)/5 (of potentially 3n-6) edges cross the spine, and every edge crosses the spine at most once; such an edge is called a biarc. We can also guarantee that all edges that cross the spine cross it in the same direction (e.g., from bottom to top). For planar 3-trees we can further improve the bound to (3n-9)/4, and for so-called Kleetopes we obtain a bound of at most (n-8)/3 edges that cross the spine. The bound for Kleetopes is tight, even if the drawing is not required to be monotone. A Kleetope is a plane triangulation that is derived from another plane triangulation T by inserting a new vertex v_f into each face f of T and then connecting v_f to the three vertices of f., Comment: Appears in the Proceedings of the 32nd International Symposium on Graph Drawing and Network Visualization (GD 2024)

In May 2023, the Georgia Tech Ethics, Technology, and Human Interaction Center organized the Conference on Ethical and Responsible Design in the National AI Institutes. Representatives from the National AI Research Institutes that had been established as of January 2023 were invited to attend; researchers representing 14 Institutes attended and participated. The conference focused on three questions: What are the main challenges that the National AI Institutes are facing with regard to the responsible design of AI systems? What are promising lines of inquiry to address these challenges? What are possible points of collaboration? Over the course of the conference, a revised version of the first question became a focal point: What are the challenges that the Institutes face in identifying ethical and responsible design practices and in implementing them in the AI development process? This document summarizes the challenges that representatives from the Institutes in attendance highlighted., Comment: 9 pages

Given a set of objects O in the plane, the corresponding intersection graph is defined as follows. A vertex is created for each object and an edge joins two vertices whenever the corresponding objects intersect. We study here the case of unit segments and polylines with exactly k bends. In the recognition problem, we are given a graph and want to decide whether the graph can be represented as the intersection graph of certain geometric objects. In previous work it was shown that various recognition problems are $\exists\mathbb{R}$-complete, leaving unit segments and polylines as few remaining natural cases. We show that recognition for both families of objects is $\exists\mathbb{R}$-complete., Comment: 17 pages, 15 figures

A graph is $2$-planar if it has local crossing number two, that is, it can be drawn in the plane such that every edge has at most two crossings. A graph is maximal $2$-planar if no edge can be added such that the resulting graph remains $2$-planar. A $2$-planar graph on $n$ vertices has at most $5n-10$ edges, and some (maximal) $2$-planar graphs -- referred to as optimal $2$-planar -- achieve this bound. However, in strong contrast to maximal planar graphs, a maximal $2$-planar graph may have fewer than the maximum possible number of edges. In this paper, we determine the minimum edge density of maximal $2$-planar graphs by proving that every maximal $2$-planar graph on $n\ge 5$ vertices has at least $2n$ edges. We also show that this bound is tight, up to an additive constant. The lower bound is based on an analysis of the degree distribution in specific classes of drawings of the graph. The upper bound construction is verified by carefully exploring the space of admissible drawings using computer support., Comment: This work (without appendix) is available at the 39th International Symposium on Computational Geometry (SoCG 2023)

For a drawing of a labeled graph, the rotation of a vertex or crossing is the cyclic order of its incident edges, represented by the labels of their other endpoints. The extended rotation system (ERS) of the drawing is the collection of the rotations of all vertices and crossings. A drawing is simple if each pair of edges has at most one common point. Gioan's Theorem states that for any two simple drawings of the complete graph $K_n$ with the same crossing edge pairs, one drawing can be transformed into the other by a sequence of triangle flips (a.k.a. Reidemeister moves of Type 3). This operation refers to the act of moving one edge of a triangular cell formed by three pairwise crossing edges over the opposite crossing of the cell, via a local transformation. We investigate to what extent Gioan-type theorems can be obtained for wider classes of graphs. A necessary (but in general not sufficient) condition for two drawings of a graph to be transformable into each other by a sequence of triangle flips is that they have the same ERS. As our main result, we show that for the large class of complete multipartite graphs, this necessary condition is in fact also sufficient. We present two different proofs of this result, one of which is shorter, while the other one yields a polynomial time algorithm for which the number of needed triangle flips for graphs on $n$ vertices is bounded by $O(n^{16})$. The latter proof uses a Carath\'eodory-type theorem for simple drawings of complete multipartite graphs, which we believe to be of independent interest. Moreover, we show that our Gioan-type theorem for complete multipartite graphs is essentially tight in the sense that having the same ERS does not remain sufficient when removing or adding very few edges., Comment: Abstract shortened for arxiv. This work (without appendix) is available at the 39th International Symposium on Computational Geometry (SoCG 2023)

An obstacle representation of a graph $G$ consists of a set of pairwise disjoint simply-connected closed regions and a one-to-one mapping of the vertices of $G$ to points such that two vertices are adjacent in $G$ if and only if the line segment connecting the two corresponding points does not intersect any obstacle. The obstacle number of a graph is the smallest number of obstacles in an obstacle representation of the graph in the plane such that all obstacles are simple polygons. It is known that the obstacle number of each $n$-vertex graph is $O(n \log n)$ [Balko, Cibulka, and Valtr, 2018] and that there are $n$-vertex graphs whose obstacle number is $\Omega(n/(\log\log n)^2)$ [Dujmovi\'c and Morin, 2015]. We improve this lower bound to $\Omega(n/\log\log n)$ for simple polygons and to $\Omega(n)$ for convex polygons. To obtain these stronger bounds, we improve known estimates on the number of $n$-vertex graphs with bounded obstacle number, solving a conjecture by Dujmovi\'c and Morin. We also show that if the drawing of some $n$-vertex graph is given as part of the input, then for some drawings $\Omega(n^2)$ obstacles are required to turn them into an obstacle representation of the graph. Our bounds are asymptotically tight in several instances. We complement these combinatorial bounds by two complexity results. First, we show that computing the obstacle number of a graph $G$ is fixed-parameter tractable in the vertex cover number of $G$. Second, we show that, given a graph $G$ and a simple polygon $P$, it is NP-hard to decide whether $G$ admits an obstacle representation using $P$ as the only obstacle.

Ferroelectric tunnel junctions (FTJ) based on hafnium zirconium oxide (Hf1-xZrxO2; HZO) are a promising candidate for future applications, such as low-power memories and neuromorphic computing. The tunneling electroresistance (TER) is tunable through the polarization state of the HZO film. To circumvent the challenge of fabricating thin ferroelectric HZO layers in the tunneling range of 1-3 nm range, ferroelectric/dielectric double layer sandwiched between two symmetric metal electrodes are used. Due to the decoupling of the ferroelectric polarization storage layer and a dielectric tunneling layer with a higher bandgap, a significant TER ratio between the two polarization states is obtained. By exploiting previously reported switching behaviour and the gradual tunability of the resistance, FTJs can be used as potential candidates for the emulation of synapses for neuromorphic computing in spiking neural networks. The implementation of two major components of a synapse are shown: long term depression/potentiation by varying the amplitude/width/number of voltage pulses applied to the artificial FTJ synapse, and spike-timing-dependent-plasticity curves by applying time-delayed voltages at each electrode. These experimental findings show the potential of spiking neural networks and neuromorphic computing that can be implemented with hafnia-based FTJs.

Crystalline materials with broken inversion symmetry can exhibit a spontaneous electric polarization, which originates from a microscopic electric dipole moment. Long-range polar or anti-polar order of such permanent dipoles gives rise to ferroelectricity or antiferroelectricity, respectively. However, the recently discovered antiferroelectrics of fluorite structure (HfO$_2$ and ZrO$_2$) are different: A non-polar phase transforms into a polar phase by spontaneous inversion symmetry breaking upon the application of an electric field. Here, we show that this structural transition in antiferroelectric ZrO$_2$ gives rise to a negative capacitance, which is promising for overcoming the fundamental limits of energy efficiency in electronics. Our findings provide insight into the thermodynamically 'forbidden' region of the antiferroelectric transition in ZrO$_2$ and extend the concept of negative capacitance beyond ferroelectricity. This shows that negative capacitance is a more general phenomenon than previously thought and can be expected in a much broader range of materials exhibiting structural phase transitions.

The area of computing with uncertainty considers problems where some information about the input elements is uncertain, but can be obtained using queries. For example, instead of the weight of an element, we may be given an interval that is guaranteed to contain the weight, and a query can be performed to reveal the weight. While previous work has considered models where queries are asked either sequentially (adaptive model) or all at once (non-adaptive model), and the goal is to minimize the number of queries that are needed to solve the given problem, we propose and study a new model where $k$ queries can be made in parallel in each round, and the goal is to minimize the number of query rounds. We use competitive analysis and present upper and lower bounds on the number of query rounds required by any algorithm in comparison with the optimal number of query rounds. Given a set of uncertain elements and a family of $m$ subsets of that set, we present an algorithm for determining the value of the minimum of each of the subsets that requires at most $(2+\varepsilon) \cdot \mathrm{opt}_k+\mathrm{O}\left(\frac{1}{\varepsilon} \cdot \lg m\right)$ rounds for every $0<\varepsilon<1$, where $\mathrm{opt}_k$ is the optimal number of rounds, as well as nearly matching lower bounds. For the problem of determining the $i$-th smallest value and identifying all elements with that value in a set of uncertain elements, we give a $2$-round-competitive algorithm. We also show that the problem of sorting a family of sets of uncertain elements admits a $2$-round-competitive algorithm and this is the best possible., Comment: An extended abstract is to appear in the proceedings of the 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021); [v2] minor fixes and typesetting

In the longest plane spanning tree problem, we are given a finite planar point set $\mathcal{P}$, and our task is to find a plane (i.e., noncrossing) spanning tree for $\mathcal{P}$ with maximum total Euclidean edge length. Despite more than two decades of research, it remains open whether this problem is NP-hard. Thus, previous efforts have focused on olynomial-time algorithms that produce plane trees whose total edge length approximates $\text{OPT}$, the maximum possible length. The approximate trees in these algorithms all have small unweighted diameter, typically three or four. It is natural to ask whether this is a common feature of longest plane spanning trees, or an artifact of the specific approximation algorithms. We provide three results to elucidate the interplay between the approximation guarantee and the unweighted diameter of the approximate trees. First, we describe a polynomial-time algorithm to construct a plane tree with diameter at most four and total edge length at least $0.546 \cdot \text{OPT}$. This constitutes a substantial improvement over the state of the art. Second, we show that a longest plane tree among those with diameter at most three can be found in polynomial time. Third, for any candidate diameter $d \geq 3$, we provide upper bounds on the approximation factor that can be achieved by a longest plane tree with diameter at most $d$ (compared to a longest plane tree without constraints)., Comment: 40 pages, 30 figures; a preliminary version appeared at SoCG 2022

We consider the computational complexity of winning this turn (mate-in-1 or "finding lethal") in Hearthstone as well as several other single turn puzzle types introduced in the Boomsday Lab expansion. We consider three natural generalizations of Hearthstone (in which hand size, board size, and deck size scale) and prove the various puzzle types in each generalization NP-hard., Comment: 17 pages, 4 appendix, 1 figure

A star-simple drawing of a graph is a drawing in which adjacent edges do not cross. In contrast, there is no restriction on the number of crossings between two independent edges. When allowing empty lenses (a face in the arrangement induced by two edges that is bounded by a 2-cycle), two independent edges may cross arbitrarily many times in a star-simple drawing. We consider star-simple drawings of $K_n$ with no empty lens. In this setting we prove an upper bound of $3((n-4)!)$ on the maximum number of crossings between any pair of edges. It follows that the total number of crossings is finite and upper bounded by $n!$., Comment: Appears in the Proceedings of the 28th International Symposium on Graph Drawing and Network Visualization (GD 2020)

Every finite graph admits a \emph{simple (topological) drawing}, that is, a drawing where every pair of edges intersects in at most one point. However, in combination with other restrictions simple drawings do not universally exist. For instance, \emph{$k$-planar graphs} are those graphs that can be drawn so that every edge has at most $k$ crossings (i.e., they admit a \emph{$k$-plane drawing}). It is known that for $k\le 3$, every $k$-planar graph admits a $k$-plane simple drawing. But for $k\ge 4$, there exist $k$-planar graphs that do not admit a $k$-plane simple drawing. Answering a question by Schaefer, we show that there exists a function $f : \mathbb{N}\rightarrow\mathbb{N}$ such that every $k$-planar graph admits an $f(k)$-plane simple drawing, for all $k\in\mathbb{N}$. Note that the function $f$ depends on $k$ only and is independent of the size of the graph. Furthermore, we develop an algorithm to show that every $4$-planar graph admits an $8$-plane simple drawing., Comment: Appears in the Proceedings of the 28th International Symposium on Graph Drawing and Network Visualization (GD 2020)

K\'{a}rolyi, Pach, and T\'{o}th proved that every 2-edge-colored straight-line drawing of the complete graph contains a monochromatic plane spanning tree. It is open if this statement generalizes to other classes of drawings, specifically, to simple drawings of the complete graph. These are drawings where edges are represented by Jordan arcs, any two of which intersect at most once. We present two partial results towards such a generalization. First, we show that the statement holds for cylindrical simple drawings. (In a cylindrical drawing, all vertices are placed on two concentric circles and no edge crosses either circle.) Second, we introduce a relaxation of the problem in which the graph is $k$-edge-colored, and the target structure must be hypochromatic, that is, avoid (at least) one color class. In this setting, we show that every $\lceil (n+5)/6\rceil$-edge-colored monotone simple drawing of $K_n$ contains a hypochromatic plane spanning tree. (In a monotone drawing, every edge is represented as an $x$-monotone curve.), Comment: Appears in the Proceedings of the 28th International Symposium on Graph Drawing and Network Visualization (GD 2020)

Motivated by the fact that in a space where shortest paths are unique, no two shortest paths meet twice, we study a question posed by Greg Bodwin: Given a geodetic graph $G$, i.e., an unweighted graph in which the shortest path between any pair of vertices is unique, is there a philogeodetic drawing of $G$, i.e., a drawing of $G$ in which the curves of any two shortest paths meet at most once? We answer this question in the negative by showing the existence of geodetic graphs that require some pair of shortest paths to cross at least four times. The bound on the number of crossings is tight for the class of graphs we construct. Furthermore, we exhibit geodetic graphs of diameter two that do not admit a philogeodetic drawing., Comment: Appears in the Proceedings of the 28th International Symposium on Graph Drawing and Network Visualization (GD 2020)

We introduce and study the problem of constructing geometric graphs that have few vertices and edges and that are universal for planar graphs or for some sub-class of planar graphs; a geometric graph is \emph{universal} for a class $\mathcal H$ of planar graphs if it contains an embedding, i.e., a crossing-free drawing, of every graph in $\mathcal H$. Our main result is that there exists a geometric graph with $n$ vertices and $O(n \log n)$ edges that is universal for $n$-vertex forests; this extends to the geometric setting a well-known graph-theoretic result by Chung and Graham, which states that there exists an $n$-vertex graph with $O(n \log n)$ edges that contains every $n$-vertex forest as a subgraph. Our $O(n \log n)$ bound on the number of edges cannot be improved, even if more than $n$ vertices are allowed. We also prove that, for every positive integer $h$, every $n$-vertex convex geometric graph that is universal for $n$-vertex outerplanar graphs has a near-quadratic number of edges, namely $\Omega_h(n^{2-1/h})$; this almost matches the trivial $O(n^2)$ upper bound given by the $n$-vertex complete convex geometric graph. Finally, we prove that there exists an $n$-vertex convex geometric graph with $n$ vertices and $O(n \log n)$ edges that is universal for $n$-vertex caterpillars., Comment: 20 pages, 8 figures; a 12-page extended abstracts of this paper will appear in the Proceedings of the 46th Workshop on Graph-Theoretic Concepts in Computer Science (WG 2020)

We show that every planar graph can be represented by a monotone topological 2-page book embedding where at most 15n/16 (of potentially 3n-6) edges cross the spine exactly once.

A simple topological graph is $k$-quasiplanar ($k\geq 2$) if it contains no $k$ pairwise crossing edges, and $k$-planar if no edge is crossed more than $k$ times. In this paper, we explore the relationship between $k$-planarity and $k$-quasiplanarity to show that, for $k \geq 2$, every $k$-planar simple topological graph can be transformed into a $(k+1)$-quasiplanar simple topological graph., Comment: arXiv admin note: substantial text overlap with arXiv:1705.05569

We initiate the study of Simultaneous Graph Embedding with Fixed Edges in the beyond planarity framework. In the QuaSEFE problem, we allow edge crossings, as long as each graph individually is drawn quasiplanar, that is, no three edges pairwise cross. We show that a triple consisting of two planar graphs and a tree admit a QuaSEFE. This result also implies that a pair consisting of a 1-planar graph and a planar graph admits a QuaSEFE. 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 QuaSEFE. Moreover, in contrast to the planar SEFE problem, we show that it is not always possible to obtain a QuaSEFE for two matchings if the quasiplanar drawing of one matching is fixed., Comment: Appears in the Proceedings of the 27th International Symposium on Graph Drawing and Network Visualization (GD 2019)

In order to have a compact visualization of the order type of a given point set S, we are interested in geometric graphs on S with few edges that unambiguously display the order type of S. We introduce the concept of exit edges, which prevent the order type from changing under continuous motion of vertices. That is, in the geometric graph on S whose edges are the exit edges, in order to change the order type of S, at least one vertex needs to move across an exit edge. Exit edges have a natural dual characterization, which allows us to efficiently compute them and to bound their number., Comment: Updated to the final version to appear in the Journal of Graph Algorithms and Applications

The ramified and stochastic evolution of dendritic microstructures has been a major issue on the safety and longevity of rechargeable batteries, particularly for the utilization high-energy metallic electrodes. We analytically develop criteria for the pulse characteristics leading to the effective halting of the ramified electrodeposits grown during extensive time scales beyond inter-ionic collisions. Our framework is based on the competitive interplay between diffusion and electromigration and tracks the gradient of ionic concentration throughout the entire cycle of pulse-rest as a critical measure for heterogeneous evolution. In particular, the framework incorporates the Brownian motion of the ions and investigates the role of the geometry of the electrodeposition interface. Our novel experimental observations verify the analytical developments, where the the dimension-free developments allows the application to the electrochemical systems of various scales., Comment: 24 Pages, 10 Figures, 3 Tables

Electropolymerization plays a critical role in the electrochemical systems. In this chapter, we address such role within the context of interplay between kinetics and energetics. The trains of chin radical reactions leads to the formation of thin films in electrochemical devices. The structure of so-called solid electrolyte interphase (SEI) during the initial charge/discharge cycles of the device of any kind (i.e. rechargeable battery) on the surface of electrode directly controls the the ultimate stability and longevity. In this chapter, we study the morphological evolution of SEI, both in terms of transport and thermodynamics within quantitative and qualitative contexts.

This paper introduces test and estimation procedures for abrupt and gradual changes in the entire jump behaviour of a discretely observed Ito semimartingale. In contrast to existing work we analyse jumps of arbitrary size which are not restricted to a minimum height. Our methods are based on weak convergence of a truncated sequential empirical distribution function of the jump characteristic of the underlying Ito semimartingale. Critical values for the new tests are obtained by a multiplier bootstrap approach and we investigate the performance of the tests also under local alternatives. An extensive simulation study shows the finite-sample properties of the new procedures., Comment: 98 pages, 13 figures