Results 1 to 10 of about 28,812 (264)
Packing Trees into 1-planar Graphs [PDF]
Journal of Graph Algorithms and Applications, 2021 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
Felice De Luca +8 more
doaj +4 more sources
The Stub Resolution of 1-planar Graphs
Journal of Graph Algorithms and Applications, 2021 The resolution of a drawing plays a crucial role when defining criteria for its quality. In the past, grid resolution, edge-length resolution, angular resolution and crossing resolution have been investigated.
Michael Kaufmann +5 more
doaj +4 more sources
1-Planarity of Graphs with a Rotation System
Journal of Graph Algorithms and Applications, 2015 A graph is 1-planar if it can be drawn in the plane such that each edge is crossed at most once. 1-planarity is known NP-hard, even for graphs of bounded bandwidth, pathwidth, or treewidth, and for near-planar graphs in which an edge is added to a planar
Christopher Auer +3 more
doaj +3 more sources
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 +2 more sources
1-Visibility Representations of 1-Planar Graphs
Journal of Graph Algorithms and Applications, 2014 A 1-visibility representation of a graph displays each vertex as a horizontal vertex-segment, called a bar, and each edge as a vertical edge-segment between the segments of the vertices, such that each edge-segment crosses at most one vertex-segment and ...
Franz Brandenburg
doaj +3 more sources
The structure and the list 3-dynamic coloring of outer-1-planar graphs [PDF]
Discrete Mathematics & Theoretical Computer Science, 2021 An outer-1-planar graph is a graph admitting a drawing in the plane so that all vertices appear in the outer region of the drawing and every edge crosses at most one other edge.
Yan Li, Xin Zhang
doaj +1 more source
Improved product structure for graphs on surfaces [PDF]
Discrete Mathematics & Theoretical Computer Science, 2022 Dujmovi\'c, Joret, Micek, Morin, Ueckerdt and Wood [J. ACM 2020] proved that for every graph $G$ with Euler genus $g$ there is a graph $H$ with treewidth at most 4 and a path $P$ such that $G\subseteq H \boxtimes P \boxtimes K_{\max\{2g,3\}}$. We improve
Marc Distel +3 more
doaj +1 more source
Correction to: Outer 1-Planar Graphs [PDF]
Algorithmica, 2021 zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Christopher Auer +6 more
openaire +1 more source
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$.
Yuanqiu Huang +2 more
openaire +4 more sources
On Optimal Beyond-Planar Graphs
Computing in Geometry and Topology, 2023 A graph is beyond-planar if it can be drawn in the plane with a specific restriction on crossings. Several types of beyond-planar graphs have been investigated, such as k-planar graphs where every edge is crossed at most k times and RAC graphs where ...
Franz Brandenburg
doaj +1 more source