Hernández-Vélez-Leaños-Salazar Graph

In the terminology adopted in this work, a Hernández-Vélez-Leaños-Salazar graph is a member of the two-parameter family of simple graphs constructed by Hernández-Vélez et al. (2017, Theorem 2) for integers . The family gives graphs with a fixed graph crossing number and arbitrarily large pseudolinear crossing number and rectilinear crossing number.

A drawing of a graph is pseudolinear if its edges can be extended to a pseudoline arrangement in which each pseudoline contains exactly one graph edge of the drawing. The pseudolinear crossing number is the minimum number of pairwise crossings in such a drawing. Every rectilinear drawing is pseudolinear, so .

Start with a graph on 14 vertices, labeled , , , ..., , , ..., . Designate as heavy the 18 edges in the two cycles with cyclic vertex orders and , together with the edges and . Here denotes the undirected edge joining vertices and . Add eight light edges, namely , , , , , , , and .

Replace each heavy graph edge by paths of two edges joining its endpoints, and replace by such paths. All internal vertices of these replacement paths are new and distinct. Leave the other seven light edges unchanged. The resulting simple graph has graph order , edge count , graph crossing number, and rectilinear crossing number satisfying

			(1)
			(2)
			(3)
			(4)
			(5)

To convert the weighted graph construction to a simple graph, each weighted graph edge is replaced by internally disjoint two-edge paths. Their internal vertices prevent the creation of multiple edges. The paths replacing are needed only when because crosses one graph edge of each in the proof, contributing of the crossings; the pairs , , and contribute the other three. When , however, is replaced by only one two-edge graph path, so the lone vertex of vertex degree 2 on that graph path is an artifact of applying the conversion uniformly. This vertex is absent from Figure 2 because that figure shows the base graph before the replacements. It can be removed by graph smoothing, restoring the graph edge . More generally, smoothing the internal vertex of any one of the replacement paths for gives a homeomorphic graph with vertices and edges, while . Although the rectilinear crossing number is not invariant under graph smoothing in general, this graph still satisfies : subdividing the restored graph edge in any rectilinear drawing of reconstructs without adding a graph crossing. The analogous statement for the pseudolinear crossing number follows from the local edge-replacement construction of Hernández-Vélez et al. (2017, Proposition 8(b)).

Thus guarantees a curvy graph. For example, and give a curvy graph of graph order 105 with 189 edges and crossing number 4. The construction does not assert that is a minimally curvy graph. However, when and , has a minimally curvy graph as a topological minor. Indeed, repeatedly passing to a proper topological minor that is still a curvy graph must terminate, since each step reduces the graph order or edge count. The resulting minimally curvy graph has crossing number at most 4, since graph crossing number does not increase when taking a topological minor. It cannot have crossing number at most 3, since then its rectilinear crossing number would equal its graph crossing number (Bienstock and Dean 1993), contradicting that it is a curvy graph. Thus has crossing number exactly 4.