Results 1 to 10 of about 380,403 (285)
4-connected 1-planar chordal graphs are Hamiltonian-connected [PDF]
arXivTutte proved that 4-connected planar graphs are Hamiltonian. It is unknown if there is an analogous result on 1-planar graphs. In this paper, we characterize 4-connected 1-planar chordal graphs, and show that all such graphs are Hamiltonian-connected. A crucial tool used in our proof is a characteristic of 1-planar 4-trees.
Licheng Zhang +3 more
arxiv +4 more sources
Three classes of 1-planar graphs [PDF]
Filomat 31 (2017) 363-370, New title: Drawing Graph Joins in the
Plane with Restrictions on Crossings, 2014 A graph is called 1-planar if it can be drawn in the plane so that each of its edges is crossed by at most one other edge. In this paper we decompose the set of all 1-planar graphs into three classes $\mathcal C_0, \mathcal C_1$ and $\mathcal C_2$ with respect to the types of crossings and present the decomposition of 1-planar join products.
Július Czap, Peter Šugerek
arxiv +5 more sources
Improvements on the density of maximal 1-planar graphs [PDF]
arXiv, 2015 A graph is 1-planar if it can be drawn in the plane such that each edge is crossed at most once. A graph, together with a 1-planar drawing is called 1-plane. Brandenburg et al. showed that there are maximal 1-planar graphs with only $\frac{45}{17}n + O(1)\approx 2.647n$ edges and maximal 1-plane graphs with only $\frac{7}{3}n+O(1)\approx 2.33n$ edges ...
János Barát, Gézá Tóth
arxiv +5 more sources
Bar 1-Visibility Drawings of 1-Planar Graphs [PDF]
arXiv, 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 horizontal line segments representing the end vertices and a vertical line segment corresponding to an ...
Shaheena Sultana +3 more
arxiv +4 more sources
On (p, 1)-Total Labelling of Some 1-Planar Graphs
Discussiones Mathematicae Graph Theory, 2021 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 paper, it is proved that the (p, 1)-total labelling number (p ≥ 2) of every 1-planar graph G is at most Δ(G) + 2p − 2 provided that Δ (G) ≥
Niu Bei, Zhang Xin
doaj +2 more sources
Compact Drawings of 1-Planar Graphs with Right-Angle Crossings and Few Bends [PDF]
International Symposium Graph Drawing and Network Visualization, 2018 We study the following classes of beyond-planar graphs: 1-planar, IC-planar, and NIC-planar graphs. These are the graphs that admit a 1-planar, IC-planar, and NIC-planar drawing, respectively. A drawing of a graph is 1-planar if every edge is crossed at most once. A 1-planar drawing is IC-planar if no two pairs of crossing edges share a vertex.
S. Chaplick +3 more
arxiv +3 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.
Xin Zhang
arxiv +3 more sources
Matchings in 1‐planar graphs with large minimum degree [PDF]
Journal of Graph Theory, 2021 In 1979, Nishizeki and Baybars showed that every planar graph with minimum degree 3 has a matching of size n3+c (where the constant c depends on the connectivity), and even better bounds hold for planar graphs with minimum degree 4 and 5.
Thérèse Biedl, John Wittnebel
openalex +3 more sources
1-Bend RAC Drawings of 1-Planar Graphs [PDF]
arXiv, 2016 A graph is 1-planar if it has a drawing where each edge is crossed at most once. A drawing is RAC (Right Angle Crossing) if the edges cross only at right angles. The relationships between 1-planar graphs and RAC drawings have been partially studied in the literature.
W. Didimo +3 more
arxiv +3 more sources
Equitable Coloring in 1-Planar Graphs [PDF]
Discrete Math. Vol. 348(2), Feb. 2025, 114286, 2023 For every $r\ge13$, we show every 1-planar graph $G$ with $\Delta(G)\le r$ has an equitable $r$-coloring.
Daniel W. Cranston, Reem Mahmoud
arxiv +3 more sources