Infinite families of crossing-critical graphs with a given crossing number

A graph is crossing-critical if deleting any edge decreases its crossing number on the plane. It is proved that, for any n ? 3, there is an infinite family of 3-connected crossing-critical graphs with crossing number n.     

On region crossing change and incidence matrix

In a recent work of Ayaka Shimizu, she studied an operation named region crossing change on link diagrams, which was proposed by Kishimoto, and showed that a region crossing change is an unknotting operation for knot diagrams. In this paper, we prove that the region crossing change on a 2-component link diagram is an unknotting operation if and only if the linking number of the diagram is even. Besides, we define an incidence matrix of a link diagram via its signed planar graph and its dual graph. By studying the relation between region crossing change and incidence matrix, we prove that a signed planar graph represents an n-component link diagram if and only if the rank of the associated incidence matrix equals c n + 1, where c denotes the size of the graph.     

SOME APPLICATIONS OF PLANAR GRAPH IN KNOT THEORY

The relationship between a link diagram and its corresponding planar graph is briefly reviewed.A necessary and sufficient condition is given to detect when a planar graph corresponds to a knot.The rela...     

Improvement on the Decay of Crossing Numbers

We prove that the crossing number of a graph decays in a “continuous fashion” in the following sense. For any ε > 0 there is a δ > 0 such that for a sufficiently large n, every graph G with n vertices and m ≥ n ^1+ε edges, has a subgraph G′ of at most (1 ? δ)m edges and crossing number at least (1 ? ε)CR(G). This generalizes the result of J. Fox and Cs. Tóth.     

Non-P-recursiveness of numbers of matchings or linear chord diagrams with many crossings

The number con_n counts matchings X on {1,2,…,2n}, which are partitions into n two-element blocks, such that the crossing graph of X is connected. Similarly, cro_n counts matchings whose crossing graph has no isolated vertex. (If it has no edge, Catalan numbers arise.) We apply generating functions techniques and prove, using a more generally applicable criterion, that the sequences (con_n) and (cro_n) are not P-recursive. On the other hand, we show that the residues of con_n and cro_n modulo any fixed power of 2 can be determined P-recursively. We consider also the numbers sco_n of symmetric connected matchings. Unfortunately, their generating function satisfies a complicated differential equation which we cannot handle.     

Planar Crossing Numbers of Graphs of Bounded Genus

Pach and Tóth proved that any n-vertex graph of genus g and maximum degree d has a planar crossing number at most c ^g dn, for a constant c>1. We improve on this result by decreasing the bound to O(dgn), and also prove that our result is tight within a constant factor. Our proof is constructive and yields an algorithm with time complexity O(dgn). As a consequence of our main result, we show a relation between the planar crossing number and the surface crossing number.     

The crossing numbers of join of the special graph on six vertices with path and cycle

There are only few results concerning crossing numbers of join of some graphs. In the paper, for the special graph H on six vertices we give the crossing numbers of its join with n isolated vertices as well as with the path P_n on n vertices and with the cycle C_n.     

Approximating the fixed linear crossing number

We present a randomized polynomial-time approximation algorithm for the fixed linear crossing number problem (FLCNP). In this problem, the vertices of a graph are placed in a fixed order along a horizontal “node line” in the plane, each edge is drawn as an arc in one of the two half-planes (pages), and the objective is to minimize the number of edge crossings. FLCNP is NP-hard, and no previous polynomial-time approximation algorithms are known. We show that the problem can be generalized to k pages and transformed to the maximum k-cut problem which admits a randomized polynomial-time approximation. For the 2-page case, our approach leads to a randomized polynomial time 0.878+0.122ρ approximation algorithm for FLCNP, where ρ is the ratio of the number of conflicting pairs (pairs of edges that cross if drawn in the same page) to the crossing number. We further investigate this performance ratio on the random graph family G_n,1/2, where each edge of the complete graph K_n occurs with probability . We show that a longstanding conjecture for the crossing number of K_n implies that with probability at least 1-4e^-λ2, the expected performance bound of the algorithm on a random graph from G_n,1/2 is 1.366+O(λ/n). A series of experiments is performed to compare the algorithm against two other leading heuristics on a set of test graphs. The results indicate that the randomized algorithm yields near-optimal solutions and outperforms the other heuristics overall.     

Edges without crossings in drawings of complete graphs

In drawings (two edges have at most one point in common, either a node or a crossing) of the complete graph K_n in the Euclidean plane there occur at most 2n ? 2 edges without crossings. This was proved by G. Ringel in [1]. Here the minimal number of edges without crossings in drawings of K_n is determined, and for the existence of values between minimum and maximum is asked.     

Vertex insertion approximates the crossing number of apex graphs

An apex graph is a graph G from which only one vertex v has to be removed to make it planar. We show that the crossing number of such G can be approximated up to a factor of Δ(G−v)⋅d(v)/2 by solving the vertex inserting problem, i.e. inserting a vertex plus incident edges into an optimally chosen planar embedding of a planar graph. Since the latter problem can be solved in polynomial time, this establishes the first polynomial fixed-factor approximation algorithm for the crossing number problem of apex graphs with bounded degree.Furthermore, we extend this result by showing that the optimal solution for inserting multiple edges or vertices into a planar graph also approximates the crossing number of the resulting graph.     

On the complexity of cell flipping in permutation diagrams and multiprocessor scheduling problems

Permutation diagrams have been used in circuit design to model a set of single point nets crossing a channel, where the minimum number of layers needed to realize the diagram equals the clique number ω(G) of its permutation graph, the value of which can be calculated in O(nlogn) time. We consider a generalization of this model motivated by “standard cell” technology in which the numbers on each side of the channel are partitioned into consecutive subsequences, or cells, each of which can be left unchanged or flipped (i.e., reversed). We ask, for what choice of flippings will the resulting clique number be minimum or maximum. We show that when one side of the channel is fixed (no flipping), an optimal flipping for the other side can be found in O(nlogn) time for the maximum clique number, and that when both sides are free this can be solved in O(n²) time. We also prove NP-completeness of finding a flipping that gives a minimum clique number, even when one side of the channel is fixed, and even when the size of the cells is restricted to be less than a small constant. Moreover, since the complement of a permutation graph is also a permutation graph, the same complexity results hold for the stable set (independence) number. In the process of the NP-completeness proof we also prove NP-completeness of a restricted variant of a scheduling problem. This new NP-completeness result may be of independent interest.     

On the maximum number of edges in quasi-planar graphs

A topological graph is quasi-planar, if it does not contain three pairwise crossing edges. Agarwal et al. [P.K. Agarwal, B. Aronov, J. Pach, R. Pollack, M. Sharir, Quasi-planar graphs have a linear number of edges, Combinatorica 17 (1) (1997) 1-9] proved that these graphs have a linear number of edges. We give a simple proof for this fact that yields the better upper bound of 8n edges for n vertices. Our best construction with 7n−O(1) edges comes very close to this bound. Moreover, we show matching upper and lower bounds for several relaxations and restrictions of this problem. In particular, we show that the maximum number of edges of a simple quasi-planar topological graph (i.e., every pair of edges have at most one point in common) is 6.5n−O(1), thereby exhibiting that non-simple quasi-planar graphs may have many more edges than simple ones.     

On k-planar crossing numbers

The k-planar crossing number of a graph is the minimum number of crossings of its edges over all possible drawings of the graph in k planes. We propose algorithms and methods for k-planar drawings of general graphs together with lower bound techniques. We give exact results for the k-planar crossing number of K_2k+1,q, for k?2. We prove tight bounds for complete graphs. We also study the rectilinear k-planar crossing number.     

On the parity of crossing numbers

For an integer n ? 1, a graph G has an n-constant crossing number if, for any two good drawings ? and ?′ of G in the plane, μ(?) ≡ μ(?′) (mod n), where μ(?) is the number of crossings in ?. We prove that, except for trivial cases, a graph G has n-constant crossing number if and only if n = 2 and G is either K_p or K_q,r, where p, q, and r are odd.     

The structure of graphs with given lengths of cycles

The cycle spectrum of a given graph G is the lengths of cycles in G. In this paper, we introduce the following problem: determining the maximum number of edges of an n-vertex graph with given cycle spectrum. In particular, we determine the maximum number of edges of an n-vertex graph without containing cycles of lengths three and at least k. This can be viewed as an extension of a well-known result of Erd?s and Gallai concerning the maximum number of edges of an n-vertex graph without containing cycles of lengths at least k. We also determine the maximum number of edges of an n-vertex graph whose cycle spectrum is a subset of two positive integers.     

On vertex symmetric digraphs

The problem of how “near” we can come to a n-coloring of a given graph is investigated. I.e., what is the minimum possible number of edges joining equicolored vertices if we color the vertices of a given graph with n colors. In its generality the problem of finding such an optimal color assignment to the vertices (given the graph and the number of colors) is NP-complete. For each graph G, however, colors can be assigned to the vertices in such a way that the number of offending edges is less than the total number of edges divided by the number of colors. Furthermore, an Ω(epn) deterministic algorithm for finding such an n-color assignment is exhibited where e is the number of edges and p is the number of vertices of the graph (e?p?n). A priori solutions for the minimal number of offending edges are given for complete graphs; similarly for equicolored K_m in K_p and equicolored graphs in K_p.     

The bondage numbers of graphs with small crossing numbers

The bondage number b(G) of a nonempty graph G is the cardinality of a smallest edge set whose removal from G results in a graph with domination number greater than the domination number γ(G) of G. Kang and Yuan proved b(G)?8 for every connected planar graph G. Fischermann, Rautenbach and Volkmann obtained some further results for connected planar graphs. In this paper, we generalize their results to connected graphs with small crossing numbers.     

On the Crossing Numbers of Products of Stars and Graphs of Order Five

 There are several known exact results on the crossing numbers of Cartesian products of paths or cycles with “small” graphs. In this paper we extend these results to the Cartesian products of two specific 5-vertex graphs with the star K _{1, n} . In addition, we give the crossing number of the graph obtained by adding two edges to the graph K _{1,4, n} in such a way that these new edges join a vertex of degree n+1 of the graph K _{1,4, n} with two its vertices of the same degree. Received: December 8, 1997 Final version received: August 14, 1998     

The crossing function of a graph

The crossing function of a graphG with orientable genusn is defined as a mapping \(f:\{ \not 0,1, \ldots ,n\} \to \{ \not 0,1,2, \ldots \} \) for whichf(k)=cr _k (G) the crossing number ofG on the orientable surface of genusk. It is proved that any decreasing convex function \(f:\{ \not 0,1, \ldots ,n\} \to \{ \not 0,1,2, \ldots \} \) with \(f(n) = \not 0\) is the crossing function of some connected graph.