FREE ELECTRONIC LIBRARY - Dissertations, online materials

«Abstract The crossing number of a graph G is the minimum num- ber of crossings in a drawing of G. We introduce several variants of this definition, ...»

Thirteen Problems on

Crossing Numbers

J´nos Pach∗


Courant Institute, NYU

and Hungarian Academy of Sciences

G´za T´th†

e o

Massachusetts Institute of Technology

and Hungarian Academy of Sciences


The crossing number of a graph G is the minimum num-

ber of crossings in a drawing of G. We introduce several

variants of this definition, and present a list of related open

problems. The first item is Zarankiewicz’s classical conjec-

ture about crossing numbers of complete bipartite graphs, the last ones are new and less carefully tested. In Section 5, we state some conjectures about the expected values of var- ious crossing numbers of random graphs, and prove a large deviation result.

1 Introduction Let G be a graph, whose vertex set and edge set are denoted by V (G) and E(G), respectively. A drawing of G is a representation of ∗ Supported by NSF grant CR-97-32101, PSC-CUNY Research Award 667339 and OTKA-T-020914.

† Supported by NSF grant DMS-99-70071, OTKA-T-020914 and OTKA-F- 22234.

1 G in the plane such that its vertices are represented by distinct points and its edges by simple continuous arcs connecting the corresponding point pairs. For simplicity, we assume that in a drawing (a) no edge passes through any vertex other than its endpoints, (b) no two edges touch each other (i.e., if two edges have a common interior point, then at this point they properly cross each other), and (c) no three edges cross at the same point.

Tur´n [23] defined the crossing number of G, cr(G), as the small- a est number of edge crossings in any drawing of G. Clearly, cr(G) = 0 if and only if G is planar.

Problem 1. (Zarankiewicz’s Conjecture [11]) The crossing number of the complete bipartite graph Kn,m with n and m vertices in its classes satisfies m m−1 n n−1 cr(Kn,m ) = · · ·.

2 2 2 2 Kleitman [13] verified this conjecture in the special case when min{m, n} ≤ 6 and Woodall [25] for m = 7, n ≤ 10.

Problem 2. Is it true that the crossing number of the complete graph Kn satisfies 1n n−1 n−2 n−3 cr(Kn ) = · · ·.

42 2 2 2 Of course, the best known upper bounds for both cr(Kn,m ) and cr(Kn ) are the conjectured values in Problems 1 and 2, respectively.

The best known lower bounds, cr(Km,n )≥ n2 m2 (1/20 − o(1)) and cr(Kn ) ≥ n4 (1/80 − o(1)), can be deduced from Kleitman’s result by an easy counting argument.

Garey and Johnson [10] proved that the determination of the crossing number is an NP-complete problem. In the past twenty years, it turned out that crossing numbers play an important role in various fields of discrete and computational geometry, and they can also be used, e.g.,to obtain lower bounds on the chip area required for the VLSI circuit layout of a graph [14].

–  –  –

4 exists and is positive.

M. Simonovits suggested that the lower bound (1) for crossing numbers may be substantially improved, if we restrict our attention to some special classes of graphs, e.g., to graphs not containing some fixed, so-called forbidden subgraph. Indeed, this turned out to be true.

A graph property P is said to be monotone if (i) for any graph G satisfying P, every subgraph of G also satisfies P; and (ii) if G1 and G2 satisfy P, then their disjoint union also satisfies P.

For any monotone property P, let ex(n, P) denote the maximum number of edges that a graph of n vertices can have if it satisfies P.

In the special case when P is the property that the graph does not contain a subgraph isomorphic to a fixed forbidden subgraph H, we write ex(n, H) for ex(n, P).

Let P be a monotone graph property with ex(n, P) = O(n1+α ) for some α 0. In [19], we proved that there exist two constants c, c 0 such that the crossing number of any graph G with property P, which has n vertices and e ≥ cn log2 n edges, satisfies e2+1/α cr(G) ≥ c. (4) n1+1/α This bound is asymptotically tight, up to a constant factor.

In some interesting special cases when we know the precise order of magnitude of the function ex(n, P), we obtained a slightly stronger result: we proved that (4) is valid for every e ≥ 4n. For instance, if P is the property that G does not contain C4, a cycle of length 4, as a subgraph, then ex(n, P) = ex(n, C4 ) = O(n3/2 ), and we know that the crossing number of any graph with n vertices and e ≥ 4n edges, which satisfies this property, is at least constant times e4 /n3. This bound is asymptotically tight.

If the answer to the following question were in the affirmative, we could extend this stronger result to many further graph properties P.

Problem 7. Let G be a bipartite graph, and let G be a graph that can be obtained from G by identifying two vertices whose distance is at least three.

Is it true that ex(n, G) = O (ex(n, G ))?

5 4 Three Other Crossing Numbers We define three variants of the notion of crossing number.

(1) The rectilinear crossing number, lin-cr(G), of a graph G is the minimum number of crossings in a drawing of G, in which every edge is represented by a straight-line segment.

(2) The pairwise crossing number of G, pair-cr(G), is the minimum number of crossing pairs of edges over all drawings of G. (Here the edges can be represented by arbitrary continuous curves, so that two edges may cross more than once, but every pair of edges can contribute at most one to pair-cr(G).) (3) The odd-crossing number of G, odd-cr(G), is the minimum number of those pairs of edges which cross an odd number of times, over all drawings of G.

It readily follows from the definitions that odd-cr(G) ≤ pair-cr(G) ≤ cr(G) ≤ lin-cr(G).

Bienstock and Dean [6] exhibited a series of graphs with crossing number 4, whose rectilinear crossing numbers are arbitrary large.

The following is perhaps the most exciting unsolved problem in the area.

Problem 8. Is it true that

odd-cr(G) = pair-cr(G) = cr(G),

for every graph G?

According to a remarkable theorem of Hanani (alias Chojnacki) [7] and Tutte [24], if a graph G can be drawn in the plane so that any pair of its edges cross an even number of times, then it can also be drawn without any crossing. In other words, odd-cr(G) = 0 implies that cr(G) = 0. Note that in this case, by a theorem of F´ry [9], we also have that lin-cr(G) = 0.

a 6 The main difficulty in this problem is that a graph has so many essentially different drawings that the computation of any of the above crossing numbers, for a graph of only 15 vertices, appears to be a hopelessly difficult task even for a very fast computer [22].

As we mentioned at the end of the Introduction, Garey and Johnson [10] showed that the determination of the crossing number is an NP-complete problem. Analogous results hold for the rectilinear crossing number [5] and for the odd-crossing number [21]. However, for the pairwise crossing number, we could prove only that it is NP-hard.

Problem 9. Given a graph G of n vertices and an integer K, can one check in polynomial time that pair-cr(G) ≤ K? In other words, is the problem of finding the pairwise crossing number of a graph in NP?

Concerning Problem 8, all we can show is that the parameters cr(G), pair-cr(G), and odd-cr(G), are not completely unrelated.

More precisely, we proved in [21] that cr(G) ≤ 2(odd-cr(G))2, for every graph G. The next step would be to answer the following question.

Problem 10. Does there exist a constant C such that cr(G) ≤ C · odd-cr(G) holds for every graph G?

–  –  –

Although we are far from knowing the expectations of crossing numbers of random graphs, it is not hard to argue that the crossing numbers are sharply concentrated in very short intervals around these values.

To show this, we need a simple observation.

Lemma. Let G be a graph with edge set E = E(G), and let G be another graph obtained from G by adding an edge. Then

–  –  –

Proof: Parts (ii) and (iii) are obviously true, because we can arbitrarily add to any optimal drawing of G an arc representing the new edge.

To prove part (i), fix a drawing of G, which minimizes the number of crossings. It is easy to see that in such a drawing any two edges have at most one point in common [22]. Add a continuous arc a representing the new edge so as to minimize the number of crossings in the resulting drawing of G.

In this new drawing, a cannot have two points, p and q, in common with any arc b representing an edge of E = E(G). Otherwise, we could replace the piece of a between p and q by an arc running very close to the piece of b between p and q. By the minimality of the initial drawing of G, this replacement would strictly decrease the number of crossings, because at least one crossing between a and b would be eliminated. This would contradict the minimality of the drawing of G. 2 Theorem. Let G(n, p) be a random graph with n vertices, with edge probability 0 p = p(n) 1, and let e = p n. Then 2

–  –  –

6 Even More Crossing Numbers

We can further modify each of the above crossing numbers, by applying one of the following rules:

Rule + : Consider only those drawings where two edges with a common endpoint do not cross each other.

Rule 0 : Two edges with a common endpoint are allowed to cross and their crossing counts.

Rule − : Two edges with a common endpoint are allowed to cross, but their crossing does not count.

10 In the previous definitions we have always used Rule 0. If we apply Rule + (Rule −) in the definition of the crossing numbers, then we indicate it by using the corresponding subscript, as shown in the table below. This gives us an array of nine different crossing numbers. It is easy to see that in a drawing of a graph, which minimizes the number of crossing points, any two edges have at most one point in common (see e.g. [22]). Therefore, cr+ (G) = cr(G), which slightly simplifies the picture.

–  –  –

[12] R. K. Guy: Crossing numbers of graphs, in: Graph theory and applications (Proc. Conf. Western Michigan Univ., Kalamazoo, Mich., 1972) Lecture Notes in Mathematics 303, Springer, Berlin, 111-124.

[13] D. J. Kleitman: The crossing number of K5,n, Journal of Combinatorial Theory 9 (1970), 315–323.

[14] T. Leighton: Complexity Issues in VLSI, Foundations of Computing Series, MIT Press, Cambridge, MA, 1983.

[15] F. T. Leighton: New lower bound techniques for VLSI, Math.

Systems Theory 17 (1984), 47–70.

[16] R. Lipton and R. Tarjan: A separator theorem for planar graphs, SIAM J. Applied Mathematics 36 (1979), 177–189.

[17] J. Pach and P.K. Agarwal: Combinatorial Geometry, J. Wiley and Sons, New York, 1995.

[18] J. Pach, F. Shahrokhi, and M. Szegedy: Applications of the crossing number, Algorithmica 16 (1996), 111–117.

–  –  –

[21] J. Pach and G. T´th: Which crossing number is it, anyway?, o in: Proceedings of the 39th Annual Symposium on Foundations of Computer Science, IEEE Press, 1998, 617-626. Also in: Journal of Combinatorial Theory, Ser. B.

13 [22] R. B. Richter and C. Thomassen: Relations between crossing numbers of complete and complete bipartite graphs, American Mathematical Monthly, February 1997, 131–137.

–  –  –

[24] W. T. Tutte: Toward a theory of crossing numbers, Journal of Combinatorial Theory 8 (1970), 45–53.

[25] D. R. Woodall: Cyclic-order graphs and Zarankiewicz’s crossing-number conjecture, Journal of Graph Theory 17 (1993), 657–671.


Similar works:


«2016/17 Dear Court Theatre Family, I first discovered the power of this art form as an undergraduate student in Los Angeles. My theatre was the Mark Taper Forum, which was the most progressive and daring theatre in the country outside of New York City: in less than two decades, the Taper produced five new plays that were awarded the Pulitzer Prize. It was on that stage I was introduced to the talent of Michael Cristofer, an actor of incredible depth and power, in three different and...»

«Welcome to the 12th Edition of the Oxfordshire Safeguarding Children Board (OSCB) ‘Safeguarding in Education’ Bulletin. This bulletin aims to promote awareness about Female Genital Mutilation (FGM) to all educational settings, to inform schools, settings and colleges of relevant news, guidance and publications, and to share feedback and learning. Please help us to share the information by circulating this bulletin to your colleagues and displaying it on notice boards in your school/college....»

«Directorate of Research Defense Equal Opportunity Management Institute 740 O’Malley Road Patrick Air Force Base, Florida 32925-3399 Observance Series Pamphlet 01-2 Photographs on the front cover are courtesy of the National Women’s Hall of Fame, at http://www.greatwomen.org/grtwmn.htm.Clockwise starting in upper left: Grace Murray Hopper (1906-1992) mathematics genius, computer pioneer, inventor, and teacher. She was the first woman to attain the rank of rear admiral in the U.S. Navy....»

«TRENDS OF LOCAL GOVERNANCE IN TIMOR-LESTE: SUCO GOVERNANCE PERFORMANCE SCALE Trends of Local Governance in Timor-Leste: Suco Governance Performance Scale (SGPS) March 2012 ACRONYMS AND ABBREVIATIONS DNAAS National Directorate for Suco Administration DNDLOT National Directorate for Local Development and Territorial Management FGD Focus Group Dialogue GEC Support for Governance, Elections and Civil Society MSATM Ministry of State Administration and Territorial Management SGPS Suco Governance...»

«18th International Congress on Project Management and Engineering Alcañiz, 16-18th July 2014 AN OVERVIEW OF THE EUROPEAN ENERGY EFFICIENCY PROGRAMMES IN THE HOUSEHOLD SECTOR Braulio Gonzalo, Marta 1; Oloke, David 2 1 Universitat Jaume I, 2 University of Wolverhampton The aim of the study is providing an overview of the main existing Energy Efficiency Programmes in the household sector around Europe. To tackle this, twelve countries have been selected, covering the five regions in Europe:...»

«1 This American Life Episode Transcript Program #375 Bad Bank Ira Glass: The news has gotten kind of confusing. I don't know if I'm allowed to say that as a person who talks here, on the public radio. It's confusing, to me. Especially all the stuff about the trouble the banks are in. You know, you turn on The Today Show at random, you can find yourself watching something like this: TAPE: As of this date, this is the second date, the static date, all these large banks exceed regulatory standards...»

«GENERAL CONDITIONS FOR SERVICES PURCHASES 1 – Contractual definitions 2 – Application and acceptance of the GENERAL CONDITIONS and CONTRACTS 3 – Scope of each CONTRACT 4 – CONTRACTOR’s Expertise and obligation of information of the PARTIES 5 – Price 6 – Payment terms and conditions 7 – Sustainable development: Safety, environment, labo(u)r and tax 8 – Consortium, Similar association 9 – Subcontracting 10 – DOCUMENTATION 11 – Follow-up, Inspection 12 – Implementation...»

«THE JAMES MACTAGGART MEMORIAL LECTURE 2008 PETER FINCHAM Thank you and thank you for inviting me. It’s an enormous honour to be asked to deliver the MacTaggart lecture. It really is one of those “are you sure you meant me?” moments. Over the years the MacTaggart has had some mighty distinguished speakers – people who have influenced television greatly, behind the screen, on the screen, beyond the screen. Ted Turner, Rupert Murdoch, Dennis Potter. Giants all of them. But just as John...»

«Improving Tropical Cyclone Intensity Forecasting With Theoretically-Based Statistical Models PI: Wayne H. Schubert Department of Atmospheric Science Colorado State University Fort Collins, CO 80523-1371 Phone: (970) 491-8521 FAX: (970) 491-8449 e-mail: waynes@atmos.colostate.edu CO-PI: Mark DeMaria NOAA/NESDIS/StAR CIRA/CSU 1375 Campus Delivery Fort Collins, CO 80523-1375 Phone: (970) 491-8405 FAX: (970) 491-8241 E-mail: Mark.DeMaria@noaa.gov CO-PI: Charles R. Sampson Naval Research Laboratory...»

«Automatic multi-document summarization for digital libraries Item type Conference Paper Authors Ou, Shiyan; Khoo, Christopher S.G.; Goh, Dion H. Citation Automatic multi-document summarization for digital libraries 2006, :72-82 Publisher School of Communication & Information, Nanyang Technological University Downloaded 16-Nov-2016 03:21:50 Link to item http://hdl.handle.net/10150/106042 Ou, S., Khoo, C. & Goh, D. (2006). Automatic multi-document summarization for digital libraries. In C....»

«Alaska The fourth quarter released by the United States Mint in 2008 commemorates the State of Alaska. It is the 49th coin to be issued in the Mint’s 50 State Quarters® Program. On January 3, 1959, Alaska became the 49th state to be admitted into the Union. The reverse of the Alaska quarter features a grizzly bear emerging from the waters clutching a salmon in its jaw. The coin’s design includes the North Star displayed above the inscription The Great Land and the inscriptions Alaska and...»

<<  HOME   |    CONTACTS
2016 www.dissertation.xlibx.info - Dissertations, online materials

Materials of this site are available for review, all rights belong to their respective owners.
If you do not agree with the fact that your material is placed on this site, please, email us, we will within 1-2 business days delete him.