Results 11 to 20 of about 192,888 (294)
Non-1-Planarity of Lexicographic Products of Graphs
Discussiones Mathematicae Graph Theory, 2021 In this paper, we show the non-1-planarity of the lexicographic product of a theta graph and K2. This result completes the proof of the conjecture that a graph G ◦ K2 is 1-planar if and only if G has no edge belonging to two cycles.
Matsumoto Naoki, Suzuki Yusuke
doaj +3 more sources
On 1-Planar Graphs with Bounded Cop-Number [PDF]
Theoretical Computer ScienceCops and Robbers is a type of pursuit-evasion game played on a graph where a set of cops try to capture a single robber. The cops first choose their initial vertex positions, and later the robber chooses a vertex. The cops and robbers make their moves in alternate turns: in the cops' turn, every cop can either choose to move to an adjacent vertex or ...
Prosenjit Bose +3 more
+6 more sources
Right Angle Crossing Graphs and 1-Planarity [PDF]
Discrete Applied Mathematics, 2011 A Right Angle Crossing Graph (also called RAC graph for short) is a graph that has a straight-line drawing where any two crossing edges are orthogonal to each other. A 1-planar graph is a graph that has a drawing where every edge is crossed at most once.
Peter Eades, Giuseppe Liotta
openalex +6 more sources
On the Sizes of Bipartite 1-Planar Graphs [PDF]
The Electronic Journal of Combinatorics, 2021 A graph is called $1$-planar if it admits a drawing in the plane such that each edge is crossed at most once. Let $G$ be a bipartite $1$-planar graph with $n$ ($n\ge 4$) vertices and $m$ edges. Karpov showed that $m\le 3n-8$ holds for even $n\ge 8$ and $m\le 3n-9$ holds for odd $n\ge 7$.
Dong, F. M. +2 more
openaire +4 more sources
Equitable Coloring in 1-Planar Graphs
Discrete Mathematics, 2023 9 ...
Daniel W. Cranston, Reem Mahmoud
openalex +4 more sources
Discrete Mathematics, 2007 AbstractA graph is 1-planar if it can be drawn on the plane so that each edge is crossed by no more than one other edge. A non-1-planar graph G is minimal if the graph G-e is 1-planar for every edge e of G. We prove that there are infinitely many minimal non-1-planar graphs (MN-graphs). It is known that every 6-vertex graph is 1-planar.
Vladimir P. Korzhik
openalex +3 more sources
Packing Trees into 1-planar Graphs [PDF]
Journal of Graph Algorithms and Applications, 2020 We introduce and study the 1-planar packing problem: Given $k$ graphs with $n$ vertices $G_1, \dots, G_k$, find a 1-planar graph that contains the given graphs as edge-disjoint spanning subgraphs. We mainly focus on the case when each $G_i$ is a tree and $k=3$.
Felice De Luca +8 more
openaire +4 more sources
Cops and Robbers on 1-Planar Graphs
, 2023 Cops and Robbers is a well-studied pursuit-evasion game in which a set of cops seeks to catch a robber in a graph G, where cops and robber move along edges of G. The cop number of G is the minimum number of cops that is sufficient to catch the robber. Every planar graph has cop number at most three, and there are planar graphs for which three cops are ...
Stéphane Durocher +8 more
openalex +4 more sources
1-Visibility Representations of 1-Planar Graphs
Journal of Graph Algorithms and Applications, 2014 A visibility representation is a classical drawing style of planar graphs. It displays the vertices of a graph as horizontal vertex-segments, and each edge is represented by a vertical edge-segment touching the segments of its end vertices; beyond that segments do not intersect.
Franz J. Brandenburg
openalex +3 more sources
Discrete Applied Mathematics, 2014 A graph is 1-planar if it can be drawn in the plane such that each of its edges is crossed at most once. We prove a conjecture of Czap and Hudak (2013) stating that the edge set of every 1-planar graph can be decomposed into a planar graph and a forest.
Eyal Ackerman
openalex +3 more sources