More Like this

1. 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
2. Drawing Shortest Paths in Geodetic Graphs

   Cornelsen, S; Pfister, M; Foerster, H; Gronemann, M; Hoffmann, M; Kobourov, S; Schneck, T (October 2020, 28th International Symposium on Graph Drawing and Network Visualization (GD))

   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. 

   more » « less
3. Universal Geometric Graphs

   https://doi.org/10.1007/978-3-030-60440-0_14  

   Frati, Fabrizio; Hoffmann, Michael; Toth, Csaba D. (October 2020, Graph-Theoretic Concepts in Computer Science (WG 2020))

   null (Ed.)

   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 universal for a class H of planar graphs if it contains an embedding, i.e., a crossing-free drawing, of every graph in H . Our main result is that there exists a geometric graph with n vertices and O(nlogn) 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(nlogn) edges that contains every n-vertex forest as a subgraph. Our O(nlogn) bound on the number of edges is asymptotically optimal. We also prove that, for every h>0 , every n-vertex convex geometric graph that is universal for the class of the n-vertex outerplanar graphs has Ωh(n2−1/h) edges; this almost matches the trivial O(n2) upper bound given by the n-vertex complete convex geometric graph. Finally, we prove that there is an n-vertex convex geometric graph with n vertices and O(nlogn) edges that is universal for n-vertex caterpillars. 

   more » « less
4. Induced subgraphs and tree decompositions III. Three-path-configurations and logarithmic treewidth

   https://doi.org/10.19086/aic.2022.6  

   Chudnovsky, Maria; Abrishami, Tara; Hajebi, Sepehr; Spirkl, Sophie (September 2022, Advances in Combinatorics)

   A _theta_ is a graph consisting of two non-adjacent vertices and three internally disjoint paths between them, each of length at least two. For a family $$\mathcal{H}$$ of graphs, we say a graph $$G$$ is $$\mathcal{H}$$-_free_ if no induced subgraph of $$G$$ is isomorphic to a member of $$\mathcal{H}$$. We prove a conjecture of Sintiari and Trotignon, that there exists an absolute constant $$c$$ for which every (theta, triangle)-free graph $$G$$ has treewidth at most $$c\log (|V(G)|)$$. A construction by Sintiari and Trotignon shows that this bound is asymptotically best possible, and (theta, triangle)-free graphs comprise the first known hereditary class of graphs with arbitrarily large yet logarithmic treewidth.Our main result is in fact a generalization of the above conjecture, that treewidth is at most logarithmic in $|V(G)|$ for every graph $$G$$ excluding the so-called _three-path-configurations_ as well as a fixed complete graph. It follows that several NP-hard problems such as Stable Set, Vertex Cover, Dominating Set and $$k$$-Coloring (for fixed $$k$$) admit polynomial time algorithms in graphs excluding the three-path-configurations and a fixed complete graph. 

   more » « less
5. Set-Coloring Ramsey Numbers via Codes

   https://doi.org/10.1556/012.2023.04302  

   Conlon, David; Fox, Jacob; He, Xiaoyu; Mubayi, Dhruv; Suk, Andrew; Verstraëte, Jacques (April 2024, Studia Scientiarum Mathematicarum Hungarica)

   For positive integers 𝑛, 𝑟, 𝑠 with 𝑟 > 𝑠, the set-coloring Ramsey number 𝑅(𝑛; 𝑟, 𝑠) is the minimum 𝑁 such that if every edge of the complete graph 𝐾_𝑁 receives a set of 𝑠 colors from a palette of 𝑟 colors, then there is guaranteed to be a monochromatic clique on 𝑛 vertices, that is, a subset of 𝑛 vertices where all of the edges between them receive a common color. In particular, the case 𝑠 = 1 corresponds to the classical multicolor Ramsey number. We prove general upper and lower bounds on 𝑅(𝑛; 𝑟, 𝑠) which imply that 𝑅(𝑛; 𝑟, 𝑠) = 2^Θ(𝑛𝑟) if 𝑠/𝑟 is bounded away from 0 and 1. The upper bound extends an old result of Erdős and Szemerédi, who treated the case 𝑠 = 𝑟 − 1, while the lower bound exploits a connection to error-correcting codes. We also study the analogous problem for hypergraphs. 

   more » « less