Results 231 to 240 of about 27,884 (262)
Some of the next articles are maybe not open access.
Light edges in 1‐planar graphs
Journal of Graph Theory, 2022AbstractA graph is 1‐planar if it can be drawn in the plane so that each edge is crossed by at most one other edge. In this paper, we prove that every 1‐planar graph with minimum degree at least 3 contains an edge with such that one of the following holds: (1) and ; (2) and ; (3) and ; (4) and ; (5) .
Juan Liu, Yiqiao Wang, Weifan Wang
openaire +1 more source
Algorithmica, 2015
zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Auer, Christopher +6 more
openaire +2 more sources
zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Auer, Christopher +6 more
openaire +2 more sources
Fáry’s Theorem for 1-Planar Graphs
2012A plane graph is a graph embedded in a plane without edge crossings. Fary’s theorem states that every plane graph can be drawn as a straight-line drawing, preserving the embedding of the plane graph. In this paper, we extend Fary’s theorem to a class of non-planar graphs.
Seok-Hee Hong +3 more
openaire +2 more sources
2020
Topological graph theory discusses, in most cases, graphs embedded in the plane (or other surfaces). For example, such plane graphs are sometimes regarded as the simplest town maps. Now, we consider a town having some pedestrian bridges, which cannot be realized by a plane graph. Its underlying graph can actually be regarded as a 1-plane graph.
openaire +1 more source
Topological graph theory discusses, in most cases, graphs embedded in the plane (or other surfaces). For example, such plane graphs are sometimes regarded as the simplest town maps. Now, we consider a town having some pedestrian bridges, which cannot be realized by a plane graph. Its underlying graph can actually be regarded as a 1-plane graph.
openaire +1 more source
Algorithms for 1-Planar Graphs
2020A 1-planar graph is a graph that can be embedded in the plane with at most one crossing per edge. It is known that testing 1-planarity of a graph is NP-complete. This chapter reviews the algorithmic results on 1-planar graphs. We first review a linear time algorithm for testing maximal 1-planarity of a graph if a rotation system (i.e., the circular ...
openaire +1 more source
Incidence Coloring of Outer-1-planar Graphs
Acta Mathematicae Applicatae Sinica, English SeriesA proper incidence $k$-coloring of a graph $G$ is a coloring of the incidences using $k$ colors in such a way that every two adjacent incidences have distinct colors. The minimum integer $k$ such that $G$ has a proper incidence $k$-coloring is the incidence chromatic number of $G$, denoted by $\chi_{i}(G)$.
Qi, Mengke, Zhang, Xin
openaire +1 more source
On the Pagenumber of 1-Planar Graphs
Chinese Annals of Mathematics, Series BzbMATH Open Web Interface contents unavailable due to conflicting licenses.
Guan, Xiaxia, Yang, Weihua
openaire +1 more source
The Vertex Arboricity of 1-Planar Graphs
Graphs and CombinatoricszbMATH Open Web Interface contents unavailable due to conflicting licenses.
Zhang, Dongdong +3 more
openaire +2 more sources
Spectral extrema of 1-planar graphs
Discrete MathematicsA graph is \(1\)-planar if it can be drawn in the plane such that each of its edges is crossed at most once. The authors study the spectral radius (i.e., largest eigenvalue of the adjacency matrix) of \(1\)-planar graphs. Firstly, an upper bound \(5+\sqrt{2n+5}\) is given for the spectral radius of an \(n\)-vertex \(1\)-planar graph with \(n\ge 7 ...
Wenqian Zhang +2 more
openaire +2 more sources