We introduce and study the 1planar packing problem: Given k graphs with n vertices πΊ1,β¦,πΊπ, find a 1planar graph that contains the given graphs as edgedisjoint spanning subgraphs. We mainly focus on the case when each πΊπ is a tree and π=3 . We prove that a triple consisting of three caterpillars or of two caterpillars and a path may not admit a 1planar packing, while two paths and a special type of caterpillar always have one. We then study 1planar packings with few crossings and prove that three paths (resp. cycles) admit a 1planar packing with at most seven (resp. fourteen) crossings. We finally show that a quadruple consisting of three paths and a perfect matching with πβ₯12 vertices admits a 1planar packing, while such a packing does not exist if πβ€10 .
The QuaSEFE Problem
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 1planar 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.
 Award ID(s):
 1712119
 Publication Date:
 NSFPAR ID:
 10109425
 Journal Name:
 International Symposium on Graph Drawing and Network Visualization
 Sponsoring Org:
 National Science Foundation
More Like this


Every finite graph admits a 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, kplanar graphs are those graphs that can be drawn so that every edge has at most k crossings (i.e., they admit a kplane drawing). It is known that for kβ€3 , every kplanar graph admits a kplane simple drawing. But for kβ₯4 , there exist kplanar graphs that do not admit a kplane simple drawing. Answering a question by Schaefer, we show that there exists a function Open image in new window such that every kplanar graph admits an f(k)plane simple drawing, for all Open image in new window. 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 4planar graph admits an 8plane simple drawing.

Given two points s and t in the plane and a set of obstacles defined by closed curves, what is the minimum number of obstacles touched by a path connecting s and t? This is a fundamental and wellstudied problem arising naturally in computational geometry, graph theory (under the names MinColor Path and Minimum Label Path), wireless sensor networks (Barrier Resilience) and motion planning (Minimum Constraint Removal). It remains NPhard even for very simpleshaped obstacles such as unitlength line segments. In this paper we give the first constant factor approximation algorithm for this problem, resolving an open problem of [Chan and Kirkpatrick, TCS, 2014] and [Bandyapadhyay et al., CGTA, 2020]. We also obtain a constant factor approximation for the Minimum Color Prize Collecting Steiner Forest where the goal is to connect multiple request pairs (s1, t1), . . . , (sk, tk) while minimizing the number of obstacles touched by any (si, ti) path plus a fixed cost of wi for each pair (si, ti) left disconnected. This generalizes the classic Steiner Forest and PrizeCollecting Steiner Forest problems on planar graphs, for which intricate PTASes are known. In contrast, no PTAS is possible for MinColor Path even on planar graphsmore »

A longstanding conjecture by Kotzig, Ringel, and Rosa states that every tree admits a graceful labeling. That is, for any tree $T$ with $n$~edges, it is conjectured that there exists a labeling $f\colon V(T) \to \{0,1,\ldots,n\}$ such that the set of induced edge labels $\bigl\{ f(u)f(v) : \{u,v\}\in E(T) \bigr\}$ is exactly $\{1,2,\ldots,n\}$. We extend this concept to allow for multigraphs with edge multiplicity at most~$2$. A \emph{2fold graceful labeling} of a graph (or multigraph) $G$ with $n$~edges is a onetoone function $f\colon V(G) \to \{0,1,\ldots,n\}$ such that the multiset of induced edge labels is comprised of two copies of each element in $\bigl\{ 1,2,\ldots, \lfloor n/2 \rfloor \bigr\}$ and, if $n$ is odd, one copy of $\bigl\{ \lceil n/2 \rceil \bigr\}$. When $n$ is even, this concept is similar to that of 2equitable labelings which were introduced by Bloom and have been studied for several classes of graphs. We show that caterpillars, cycles of length $n \not\equiv 1 \pmod{4}$, and complete bipartite graphs admit 2fold graceful labelings. We also show that under certain conditions, the join of a tree and an empty graph (i.e., a graph with vertices but no edges) is $2$fold graceful.

We introduce a model for ant trail formation, building upon previous work on biologically feasible local algorithms that plausibly describe how ants maintain trail networks. The model is a variant of a reinforced random walk on a directed graph, where ants lay pheromone on edges as they traverse them and the next edge to traverse is chosen based on the level of pheromone; this pheromone decays with time. There is a bidirectional flow of ants in the network: the forward flow proceeds along forward edges from source (e.g. the nest) to sink (e.g. a food source), and the backward flow in the opposite direction. Some fraction of ants are lost as they pass through each node (modeling the loss of ants due to exploration observed in the field). We initiate a theoretical study of this model. We note that ant navigation has inspired the field of ant colony optimization, heuristics that have been applied to several combinatorial optimization problems; however the algorithms developed there are considerably more complex and not constrained to being biologically feasible. We first consider the linear decision rule, where the flow divides itself among the next set of edges in proportion to their pheromone level. Here,more »