Crossing-Critical Graphs and Path-Width

Hlinený, Petr (2002) Crossing-Critical Graphs and Path-Width. In: Graph Drawing 9th International Symposium, GD 2001, September 23-26, 2001, Vienna, Austria , pp. 102-114 (Official URL: http://dx.doi.org/10.1007/3-540-45848-4_9).

Full text not available from this repository.

Abstract

The crossing number cr( $G$) of a graph $G$, is the smallest possible number of edge-crossings in a drawing of $G$ in the plane. A graph $G$ is crossing-critical if cr ( $G$-e)$<({\rm cr}$ $G$) for all edges $e$ of $G$. G. Salazar conjectured in 1999 that crossing-critical graphs have path-width bounded by a function of their crossing number, which roughly means that such graphs are made up of small pieces joined in a linear way on small cut-sets. That conjecture was recently proved by the author [9]. Our paper presents that result together with a brief sketch of proof ideas. The main focus of the paper is on presenting a new construction of crossing-critical graphs, which, in particular, gives a nontrivial lower bound on the path-width. Our construction may be interesting also to other areas concerned with the crossing number.

Item Type:Conference Paper
Additional Information:10.1007/3-540-45848-4_9
Classifications:Z Theory > Z.001 General
G Algorithms and Complexity > G.420 Crossings
ID Code:505

Repository Staff Only: item control page

References

M. Ajtai, V. Chvátal, M. Newborn, E. Szemerédi. Crossing-free subgraphs. Theory and Practice of Combinatorics, 9-12, North-Holland Math. Stud. 60, North-Holland, Amsterdam-New York, 1982.

D. Bienstock, N. Robertson, P. Seymour, R. Thomas. Quickly excluding a forest. J. Combin. Theory serie B 52 (1991), 274-283.

S. N. Bhatt and F. T. Leighton. A framework for solving VLSI layout problems. Journal of Computer and System Sciences, 28:300-343, 1984.

G. Di Battista, P. Eades, R. Tamassia, and I. G. Tollis. Graph Drawing: Algorithms for the Visualization of Graphs. Prentice-Hall, New Jersey, 1999.

C. Ding, B. Oporowski, R. Thomas, and D. Vertigan. Large four-connected nonplanar graphs. in preparation.

M.R. Garey and D.S. Johnson. Crossing number is np-complete, SIAM J. Algebraic and Discrete Methods 4(1983), 312-316.

J. Geelen, B. Richter, G. Salazar. Embedding grids on surfaces, manuscript.

L.Y. Glebsky and G. Salazar. The conjecture cr(C_m \times C_n)=(m-2)n is true for all but finitely n, for each m, submitted.

P. Hlinený. Crossing-number critical graphs have bounded path-width, submitted. http://www.mcs.vuw.ac.nz/~hlineny/doc/crpath2.ps.gz

M. Kochol. Construction of crossing-critical graphs. Discrete Math. 66(1987), 311-313.

T. Leighton. Complexity Issues in VLSI. Foundation of Computing Series, MIT Press, Cambridge, MA, 1983.

P. Mutzel and T. Zeigler. The constrained crossing minimization problem. In J. Kratochvíl, editor, Graph Drawing Conference, volume 1731 of Lecture Notes in Computer Science, pages 175-185. Springer-Verlag, 1999.

J. Pach and G. Tóth. Which crossing number is it, anyway? Proc. 39th Foundations of Computer Science (1998), IEEE Press 1999, 617-626.

H. Purchase. Which aesthetichas the greatest effect on human understanding? In G. Di Battista, ed., Proc. of the Symp. on Graph Drawing, GD'97, vol. 1353 of LNCS, pages 248-261. Springer Verlag, 1997.

R. B. Richter and C. Thomassen. Intersections of curve systems and the crossing number of C_5 \times C_5. Discrete comput. Geom. 13 (1995), 149-159.

R. Richter and G. Salazar. The crossing number of C_6 \times C_n, Australas. J. Combin. 23 (2001), 135-143.

N. Robertson, P. Seymour. Graph minors I. Excluding a forest, J. Combin. Ser. B 35 (1983), 39-61.

F. Shahrokhi and I. Vrt'o. On 3-layer Crossings and pseudo arrangements. In J. Kratochvíl, editor, Graph Drawing Conference, volume 1731 of Lecture Notes in Computer Science, pages 225-231. Springer-Verlag, 1999.

W. T. Tutte, Toward a theory of crossing numbers, J. Combinatorial Theory 8 (1970), 45-53.