Yuanqiu Huang
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Research Subjects
Research Interests
Yuanqiu Huang has a total of 24 co-authors. Here are the top co-authors by number of shared publications:
- Licheng Zhang
School of Mathematics Hunan University 410082 Changsha P.R.China
13 shared publications - Fengming Dong
National Institute of Education, Nanyang Technological University, Singapore, Singapore
10 shared publications - Zhangdong Ouyang
Department of Mathematics Hunan First Normal University 410205 Changsha P.R.China
9 shared publications - Zongpeng Ding
Hunan First Normal Univ, Sch Math & Stat, Changsha 410205, Peoples R China
5 shared publications - Guanghua Dong
Tianjin Polytechnic University
2 shared publications - Guiping Wang
College of Mathematics and Statistics Hunan Normal University 410081 Changsha P.R.China
2 shared publications
Latest Publications
- 1 January 2026
- Published by University of Zielona Góra, Poland in Discussiones Mathematicae Graph Theory
- Vol. 46 (3) , 765
The minimum size of maximal bipartite IC-plane graphs with given connectivity
- 1 January 2026
- Published by University of Zielona Góra, Poland in Discussiones Mathematicae Graph Theory
- Vol. 46 (3) , 765
The minimum size of maximal bipartite IC-plane graphs with given connectivity
- Open Access
Maximal 1-plane graphs with the maximum number of crossings
A drawing of a graph in the plane is called 1-planar if each edge is crossed at most once. A graph together with a 1-planar drawing is a 1-plane graph. A 1-plane graph $G$ with exactly $4|V (G)|-8$ edges is called optimal. The crossing number $cr(G)$ of a graph $G$ is the minimum number of crossings over all drawings of $G$. Czap and Hudák proved that $cr(G)\le |V(G)|-2$ for any 1-plane graph $G$ and equality holds if $G$ is an optimal 1-plane graph [The Electronic J. Comb}., 20(2),#P54 (2013)]. This paper aims to characterize maximal 1-plane graphs $G$ achieving the maximum crossing number $|V(G)|-2$. We first introduce a class of quasi-optimal 1-plane graphs as a generalization of optimal 1-plane graphs, and then prove that for any maximal 1-plane graph $G$, $cr(G)=|V(G)|-2$ holds if and only if $G$ is a quasi-optimal 1-plane graph. Moreover, we prove that every quasi-optimal 1-plane graph is maximal 1-planar (not merely drawing-saturated). Finally, we present some applications of our main results, including a disproof of an upper bound on the crossing number of maximal 1-planar graphs with odd-degree vertices.Open AccessMaximal 1-plane graphs with the maximum number of crossings
A drawing of a graph in the plane is called 1-planar if each edge is crossed at most once. A graph together with a 1-planar drawing is a 1-plane graph. A 1-plane graph $G$ with exactly $4|V (G)|-8$ edges is called optimal. The crossing number $cr(G)$ of a graph $G$ is the minimum number of crossings over all drawings of $G$. Czap and Hudák proved that $cr(G)\le |V(G)|-2$ for any 1-plane graph $G$ and equality holds if $G$ is an optimal 1-plane graph [The Electronic J. Comb}., 20(2),#P54 (2013)]. This paper aims to characterize maximal 1-plane graphs $G$ achieving the maximum crossing number $|V(G)|-2$. We first introduce a class of quasi-optimal 1-plane graphs as a generalization of optimal 1-plane graphs, and then prove that for any maximal 1-plane graph $G$, $cr(G)=|V(G)|-2$ holds if and only if $G$ is a quasi-optimal 1-plane graph. Moreover, we prove that every quasi-optimal 1-plane graph is maximal 1-planar (not merely drawing-saturated). Finally, we present some applications of our main results, including a disproof of an upper bound on the crossing number of maximal 1-planar graphs with odd-degree vertices. - Open Access
The minimum size of maximal bipartite IC-plane graphs with given connectivity
Recently, the problem of establishing bounds on the edge density of 1-planar graphs, including their subclass IC-planar graphs, has received considerable attention. In 2018, Angelini et al. showed that any n-vertex bipartite IC-planar graph has at most 2.25n-4 edges, which implies that bipartite IC-planar graphs have vertex-connectivity at most 4. In this paper, we prove that any n-vertex maximal bipartite IC-plane graph with connectivity 2 has at least 3/2n-2 edges, and those with connectivity 3 has at least 2n-3 edges. All the above lower bounds are tight. For 4-connected maximal bipartite IC-planar graphs, the question of determining a non-trivial lower bound on the size remains open.
Open AccessThe minimum size of maximal bipartite IC-plane graphs with given connectivity
Recently, the problem of establishing bounds on the edge density of 1-planar graphs, including their subclass IC-planar graphs, has received considerable attention. In 2018, Angelini et al. showed that any n-vertex bipartite IC-planar graph has at most 2.25n-4 edges, which implies that bipartite IC-planar graphs have vertex-connectivity at most 4. In this paper, we prove that any n-vertex maximal bipartite IC-plane graph with connectivity 2 has at least 3/2n-2 edges, and those with connectivity 3 has at least 2n-3 edges. All the above lower bounds are tight. For 4-connected maximal bipartite IC-planar graphs, the question of determining a non-trivial lower bound on the size remains open.
- Open Access
The minimum crossing number and minimum size of maximal 1-plane graphs with given connectivity
A 1-planar graph is a graph which has a drawing on the plane such that each edge is crossed at most once. If a 1-planar graph is drawn in that way, the drawing is called a {\it 1-plane graph}. A graph is maximal 1-plane (or 1-planar) if no additional edge can be added without violating 1-planarity or simplicity. It is known that any maximal 1-plane graph is $k$-connected for some $k$ with $2\le k\le 7$. Recently, Huang et al. proved that any maximal 1-plane graph with $n$ ($\ge 5$) vertices has at least $\lceil\frac{7}{3}n\rceil-3$ edges, which is tight for all integers $n\ge 5$. In this paper, we study $k$-connected maximal 1-plane graphs for each $k$ with $3\le k\le 7$, and establish a lower bound for their crossing numbers and a lower bound for their edge numbers, respectively.Open AccessThe minimum crossing number and minimum size of maximal 1-plane graphs with given connectivity
A 1-planar graph is a graph which has a drawing on the plane such that each edge is crossed at most once. If a 1-planar graph is drawn in that way, the drawing is called a {\it 1-plane graph}. A graph is maximal 1-plane (or 1-planar) if no additional edge can be added without violating 1-planarity or simplicity. It is known that any maximal 1-plane graph is $k$-connected for some $k$ with $2\le k\le 7$. Recently, Huang et al. proved that any maximal 1-plane graph with $n$ ($\ge 5$) vertices has at least $\lceil\frac{7}{3}n\rceil-3$ edges, which is tight for all integers $n\ge 5$. In this paper, we study $k$-connected maximal 1-plane graphs for each $k$ with $3\le k\le 7$, and establish a lower bound for their crossing numbers and a lower bound for their edge numbers, respectively. - 18 April 2025
- Published by Wiley in Journal of Graph Theory
- Vol. 110 (1) , 72-81
4‐Connected 1‐Planar Chordal Graphs Are Hamiltonian‐Connected
Tutte 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.
- 18 April 2025
- Published by Wiley in Journal of Graph Theory
- Vol. 110 (1) , 72-81
4‐Connected 1‐Planar Chordal Graphs Are Hamiltonian‐Connected
Tutte 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.
- Open Access
Determining the minimum size of maximal 1-plane graphs
A 1-plane graph is a graph together with a drawing in the plane in such a way that each edge is crossed at most once. A 1-plane graph is maximal if no edge can be added without violating either 1-planarity or simplicity. Let $m(n)$ denote the minimum size of a maximal $1$-plane graph of order $n$. Brandenburg et al. established that $m(n)\ge 2.1n-\frac{10}{3}$ for all $n\ge 4$, which was improved by Barát and Tóth to $m(n)\ge \frac{20}{9}n-\frac{10}{3}$. In this paper, we confirm that $m(n)=\left\lceil\frac{7}{3}n\right\rceil-3$ for all $n\ge 5$.Open AccessDetermining the minimum size of maximal 1-plane graphs
A 1-plane graph is a graph together with a drawing in the plane in such a way that each edge is crossed at most once. A 1-plane graph is maximal if no edge can be added without violating either 1-planarity or simplicity. Let $m(n)$ denote the minimum size of a maximal $1$-plane graph of order $n$. Brandenburg et al. established that $m(n)\ge 2.1n-\frac{10}{3}$ for all $n\ge 4$, which was improved by Barát and Tóth to $m(n)\ge \frac{20}{9}n-\frac{10}{3}$. In this paper, we confirm that $m(n)=\left\lceil\frac{7}{3}n\right\rceil-3$ for all $n\ge 5$. - Open Access
The minimum size of 2-connected chordal bipartite graphs
A bipartite graph is chordal bipartite if every cycle of length at least six contains a chord. We determine the minimum size in 2-connected chordal bipartite graphs with given order.
Open AccessThe minimum size of 2-connected chordal bipartite graphs
A bipartite graph is chordal bipartite if every cycle of length at least six contains a chord. We determine the minimum size in 2-connected chordal bipartite graphs with given order.
- 17 October 2024
- Published by World Scientific Pub Co Pte Ltd in International Journal of Foundations of Computer Science
- Vol. 36 (04) , 569-582
The Generalized 3-Connectivity of a Family of Regular Networks
The generalized [ ]-connectivity of a graph [ ], denoted by [ ], is the minimum number of internally edge disjoint [ ]-trees for any [ ] with [ ]. The generalized [ ]-connectivity of a graph is a natural extension of the classical connectivity and can be served as an essential parameter for measuring reliability and fault tolerance of the network. Hierarchical interconnection networks (HIN’s) are very important in applications related to the modern interconnection networks since they posses many desirable properties. In this paper, we firstly introduce a family of regular networks [ ] that can be obtained from [ ] by adding a matching, where [ ] and [ ] are vertex-disjoint subgraphs and each [ ] is isomorphic to a given graph [ ] ([ ]). Then we determine the generalized 3-connectivity of [ ]. As applications of the main result, the generalized 3-connectivity of some HIN’s, such as the hierarchical star network [ ], the hierarchical cubic network [ ] and the hierarchical folded hypercube [ ], can be determined immediately.
- 17 October 2024
- Published by World Scientific Pub Co Pte Ltd in International Journal of Foundations of Computer Science
- Vol. 36 (04) , 569-582
The Generalized 3-Connectivity of a Family of Regular Networks
The generalized [ ]-connectivity of a graph [ ], denoted by [ ], is the minimum number of internally edge disjoint [ ]-trees for any [ ] with [ ]. The generalized [ ]-connectivity of a graph is a natural extension of the classical connectivity and can be served as an essential parameter for measuring reliability and fault tolerance of the network. Hierarchical interconnection networks (HIN’s) are very important in applications related to the modern interconnection networks since they posses many desirable properties. In this paper, we firstly introduce a family of regular networks [ ] that can be obtained from [ ] by adding a matching, where [ ] and [ ] are vertex-disjoint subgraphs and each [ ] is isomorphic to a given graph [ ] ([ ]). Then we determine the generalized 3-connectivity of [ ]. As applications of the main result, the generalized 3-connectivity of some HIN’s, such as the hierarchical star network [ ], the hierarchical cubic network [ ] and the hierarchical folded hypercube [ ], can be determined immediately.
- Open Access
4-connected 1-planar chordal graphs are Hamiltonian-connected
Tutte 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.
Open Access4-connected 1-planar chordal graphs are Hamiltonian-connected
Tutte 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.
- Open Access
A new infinite family of 4-regular crossing-critical graphs
A graph $G$ is said to be crossing-critical if $cr(G-e)< cr(G)$ for every edge $e$ of $G$, where $cr(G)$ is the crossing number of $G$. Richter and Thomassen [Journal of Combinatorial Theory, Series B 58 (1993), 217-224] constructed an infinite family of 4-regular crossing-critical graphs with crossing number $3$. In this article, we present a new infinite family of 4-regular crossing-critical graphs.Open AccessA new infinite family of 4-regular crossing-critical graphs
A graph $G$ is said to be crossing-critical if $cr(G-e)< cr(G)$ for every edge $e$ of $G$, where $cr(G)$ is the crossing number of $G$. Richter and Thomassen [Journal of Combinatorial Theory, Series B 58 (1993), 217-224] constructed an infinite family of 4-regular crossing-critical graphs with crossing number $3$. In this article, we present a new infinite family of 4-regular crossing-critical graphs.