Results 1 to 10 of about 533,998 (325)
Minimal non-1-planar graphs [PDF]
Discrete Mathematics, 2008 A 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.
Korzhik, Vladimir P.
core +4 more sources
Class two 1-planar graphs with maximum degree six or seven [PDF]
arXiv, 2011 A graph is 1-planar if it can be drawn on the plane so that each edge is crossed by at most one other edge. In this note we give examples of class two 1-planar graphs with maximum degree six or seven.Comment: 3 pages, 2 ...
Zhang, Xin
core +4 more sources
Acyclic Chromatic Index of 1-Planar Graphs [PDF]
Mathematics, 2022 The acyclic chromatic index χa′(G) of a graph G is the smallest k for which G is a proper edge colorable using k colors. A 1-planar graph is a graph that can be drawn in plane such that every edge is crossed by at most one other edge.
Wanshun Yang +5 more
doaj +3 more sources
Bar 1-Visibility Drawings of 1-Planar Graphs
International Conference on Applied Algorithms, 2013 A bar 1-visibility drawing of a graph $G$ is a drawing of $G$ where each vertex is drawn as a horizontal line segment called a bar, each edge is drawn as a vertical line segment where the vertical line segment representing an edge must connect the ...
A.M. Dean +13 more
core +4 more sources
Bar 1-Visibility Graphs and their relation to other Nearly Planar Graphs [PDF]
, 2013 A graph is called a strong (resp. weak) bar 1-visibility graph if its vertices can be represented as horizontal segments (bars) in the plane so that its edges are all (resp.
Evans, William +5 more
core +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
Mathematical Modelling and Control, 2021 In this paper, we study the problem of partitioning the vertex set of a planar graph with girth restriction into parts, also referred to as color classes, such that each part induces a graph with components of bounded order.
Chunyu Tian, Lei Sun
doaj +1 more source
Skewness and the crossing numbers of graphs
AIMS Mathematics, 2023 The skewness of a graph $ G $, $ sk(G) $, is the smallest number of edges that need to be removed from $ G $ to make it planar. The crossing number of a graph $ G $, $ cr(G) $, is the minimum number of crossings over all possible drawings of $ G $. There
Zongpeng Ding
doaj +1 more source
Equitable Coloring of IC-Planar Graphs with Girth g ≥ 7
Axioms, 2023 An equitable k-coloring of a graph G is a proper vertex coloring such that the size of any two color classes differ at most 1. If there is an equitable k-coloring of G, then the graph G is said to be equitably k-colorable.
Danjun Huang, Xianxi Wu
doaj +1 more source