We introduce and study the 1-planar packing problem: Given k graphs with n vertices πΊ1,β¦,πΊπ, find a 1-planar graph that contains the given graphs as edge-disjoint 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 1-planar packing, while two paths and a special type of caterpillar always have one. We then study 1-planar packings with few crossings and prove that three paths (resp. cycles) admit a 1-planar 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 1-planar packing, while such a packing does not exist if πβ€10 .
more »
« less
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 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
- Award ID(s):
- 1712119
- NSF-PAR ID:
- 10109425
- Date Published:
- Journal Name:
- International Symposium on Graph Drawing and Network Visualization
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
null (Ed.)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, k-planar graphs are those graphs that can be drawn so that every edge has at most k crossings (i.e., they admit a k-plane drawing). It is known that for kβ€3 , every k-planar graph admits a k-plane simple drawing. But for kβ₯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 Open image in new window such that every k-planar 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 4-planar graph admits an 8-plane simple drawing.more » « less
-
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
-
null (Ed.)A long-standing 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{2-fold graceful labeling} of a graph (or multigraph) $G$ with $n$~edges is a one-to-one 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 2-equitable 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 2-fold 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.more » « less
-
null (Ed.)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, we show that the process converges to the path with minimum leakage when the forward and backward flows do not change over time. On the other hand, when the forward and backward flows increase over time (caused by positive reinforcement from the discovery of a food source, for example), we show that the process converges to the shortest path. These results are for graphs consisting of two parallel paths (a case that has been investigated before in experiments). Through simulations, we show that these results hold for more general graphs drawn from various random graph models; proving this convergence in the general case is an interesting open problem. Further, to understand the behaviour of other decision rules beyond the linear rule, we consider a general family of decision rules. For this family, we show that there is no advantage of using a non-linear decision rule, if the goal is to find the shortest or the minimum leakage path. We also show that bidirectional flow is necessary for convergence to such paths. Our results provide a plausible explanation for field observations, and open up new avenues for further theoretical and experimental investigation.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Conference Paper:
- The DOI is not currently available.
