YHYuanqiu Huang

Yuanqiu Huang

*This is an algorithmically generated author record based on publicly available information.

Current Organizations / Institutes

The organizations/institutes from the scholar's latest article


Yuanqiu Huang has a total of 24 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Open Access

    Maximal 1-plane graphs with the maximum number of crossings

    by Zhangdong Ouyang, Yuanqiu Huang, Licheng Zhang

    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

    by Guiping Wang, Yuanqiu Huang, Zhangdong Ouyang, Licheng Zhang

    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

    by Zhangdong Ouyang, Yuanqiu Huang, Licheng Zhang, Fengming Dong

    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.

  • 4‐Connected 1‐Planar Chordal Graphs Are Hamiltonian‐Connected

    by Licheng Zhang, Yuanqiu Huang, Shengxiang Lv, Fengming Dong

    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

    by Yuanqiu Huang, Zhangdong Ouyang, Licheng Zhang, Fengming Dong

    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

    by Licheng Zhang, Yuanqiu Huang

    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.

  • The Generalized 3-Connectivity of a Family of Regular Networks

    by Jing Wang, Xidao Luan, Yuanqiu Huang

    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

    by Licheng Zhang, Yuanqiu Huang, Shengxiang Lv, Fengming Dong

    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

    by Zongpeng Ding, Yuanqiu Huang, Fengming Dong

    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.