Results 11 to 20 of about 27,017 (285)
Straight-line Drawings of 1-Planar Graphs [PDF]
Computational Geometry, 2021 A graph is 1-planar if it can be drawn in the plane so that each edge is crossed at most once. However, there are 1-planar graphs which do not admit a straight-line 1-planar drawing. We show that every 1-planar graph has a straight-line drawing with a two-coloring of the edges, so that edges of the same color do not cross.
Franz J. Brandenburg
openalex +3 more sources
Counting cliques in 1-planar graphs
European Journal of Combinatorics, 2022 The problem of maximising the number of cliques among n-vertex graphs from various graph classes has received considerable attention. We investigate this problem for the class of 1-planar graphs where we determine precisely the maximum total number of cliques as well as the maximum number of cliques of any fixed size. We also precisely characterise the
J. Pascal Gollin +4 more
openalex +6 more sources
Joins of 1-planar graphs [PDF]
Acta Mathematica Sinica, English Series, 2014 A graph is called 1-planar if there exists its drawing in the plane such that each edge is crossed at most once. In this paper, we study 1-planar graph joins. We prove that the join $G+H$ is 1-planar if and only if the pair $[G,H]$ is subgraph-majorized (that is, both $G$ and $H$ are subgraphs of graphs of the major pair) by one of pairs $[C_3 \cup C_3,
Július Czap +5 more
+6 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. In this paper, we investigate the stub resolution, a recently introduced criterion for nonplanar drawings. Intersection points divide edges into
Michael Kaufmann +5 more
openalex +3 more sources
Correction to: Outer 1-Planar Graphs [PDF]
Algorithmica, 2021 zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Auer, Christopher +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$.
Dong, F. M. +2 more
openaire +4 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 +2 more sources
Right Angle Crossing Graphs and 1-Planarity [PDF]
Discrete Applied Mathematics, 2011 zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Peter Eades, Giuseppe Liotta
openalex +5 more sources
A Note on Odd Colorings of 1-Planar Graphs [PDF]
Discrete Applied Mathematics, 2022 A proper coloring of a graph is odd if every non-isolated vertex has some color that appears an odd number of times on its neighborhood. This notion was recently introduced by Petruševski and Škrekovski, who proved that every planar graph admits an odd $9$-coloring; they also conjectured that every planar graph admits an odd $5$-coloring. Shortly after,
Daniel W. Cranston +2 more
openalex +3 more sources
From light edges to strong edge-colouring of 1-planar graphs [PDF]
Discrete Mathematics & Theoretical Computer Science, 2020 A strong edge-colouring of an undirected graph $G$ is an edge-colouring where every two edges at distance at most~$2$ receive distinct colours. The strong chromatic index of $G$ is the least number of colours in a strong edge-colouring of $G$.
Julien Bensmail +3 more
doaj +1 more source