Crossing and Weighted Crossing Number of Near-Planar Graphs

Cabello, Sergio and Mohar, Bojan (2009) Crossing and Weighted Crossing Number of Near-Planar Graphs. In: Graph Drawing 16th International Symposium, GD 2008, September 21- 24, 2008, Heraklion, Crete, Greece , pp. 38-49 (Official URL: http://dx.doi.org/10.1007/978-3-642-00219-9_5).

Full text not available from this repository.

Abstract

A nonplanar graph G is near-planar if it contains an edge e such that G − e is planar. The problem of determining the crossing number of a near-planar graph is exhibited from different combinatorial viewpoints. On the one hand, we develop min-max formulas involving efficiently computable lower and upper bounds. These min-max results are the first of their kind in the study of crossing numbers and improve the approximation factor for the approximation algorithm given by Hlinˇny e´ and Salazar (Graph Drawing GD 2006). On the other hand, we show that it is NP-hard to compute a weighted version of the crossing number for near-planar graphs.

Item Type:Conference Paper
Additional Information:10.1007/978-3-642-00219-9_5
Classifications:G Algorithms and Complexity > G.420 Crossings
ID Code:895

Repository Staff Only: item control page

References

Bhatt, S.N., Leighton, F.T.: A framework for solving VLSI graph layout problems. J. Comput. System Sci. 28(2), 300–343 (1984)

Bokal, D., Fijavz, G., Mohar, B.: The minor crossing number. SIAM J. Discret. z Math. 20(2), 344–356 (2006)

Garey, M.R., Johnson, D.S.: Crossing number is NP-complete. SIAM J. Alg. Discr. Meth. 4, 312–316 (1983)

Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman & Co.,New York, NY, USA (1979)

Gutwenger, C., Mutzel, P., Weiskircher, R.: Inserting an edge into a planar graph. Algorithmica 41, 289–308 (2005)

Hlineny, P., Salazar, G.: On the crossing number of almost planar graphs. In: Kaufmann, M., Wagner, D. (eds.) GD 2006. Lecture Notes in Computer Science, vol. 4372, pp. 162–173. Springer (2007)

Juvan, M., Marincek, J., Mohar, B.: Elimination of local bridges. Math. Slovaca c 47, 85–92 (1997)

Leighton, F.T.: Complexity issues in VLSI. MIT Press, Cambridge, MA, USA (1983)

Leighton, F.T.: New lower bound techniques for vlsi. Math. Systems Theory 17, 47–70 (1984)

Liebers, A.: Planarizing graphs—a survey and annotated bibliography. J. Graph Algorithms Appl. 5, 74pp. (2001)

Mishra, B., Tarjan, R.E.: A linear-time algorithm for finding an ambitus. Algorithmica 7(5&6), 521–554 (1992)

Mohar, B., Thomassen, C.: Graphs on Surfaces. Johns Hopkins University Press, Baltimore (2001)

Mohar, B.: On the crossing number of almost planar graphs. Informatica 30, 301– 303 (2006)

Riskin, A.: The crossing number of a cubic plane polyhedral map plus an edge. Studia Sci. Math. Hungar. 31, 405–413 (1996)

Shahrokhi, F., Sýkora, O., Székely, L.A., Vrt’o, I.: Crossing numbers: bounds and applications. In: Barany, I., Böröczky, K. (eds.) Intuitive geometry (Budapest, oo 1995). Bolyai Society Mathematical Studies, vol. 6, pp. 179–206. Akademia Kiado (1997)

Székely, L.A.: A successful concept for measuring non-planarity of graphs: The e crossing number. Discrete Math. 276, 331–352 (2004)

Tutte, W.T.: Separation of vertices by a circuit. Discrete Math. 12, 173–184 (1975)

Vrt’o, I.: Crossing number of graphs: A bibliography, ftp://ftp.ifi.savba.sk/ pub/imrich/crobib.pdf