Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Bücher
Zeitschriften
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
MTZ-Fachkongress

Antriebe und Energiesysteme von morgen


Austausch von Automobil- und Energiewirtschaft

Am 14./15. Mai geht es in Chemnitz um die Mobilitätswende durch Elektro- und Wasserstofffahrzeuge.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
Introduction Kapitel lesen Erstes Kapitel lesen

2013 | OriginalPaper | Buchkapitel

The Rectilinear Crossing Number of K n : Closing in (or Are We?)

verfasst von : Bernardo M. Ábrego, Silvia Fernández-Merchant, Gelasio Salazar

Erschienen in: Thirty Essays on Geometric Graph Theory

Verlag: Springer New York

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

The calculation of the rectilinear crossing number of complete graphs is an important open problem in combinatorial geometry, with important and fruitful connections to other classical problems. Our aim in this chapter is to survey the body of knowledge around this parameter.
Mathematics Subject Classification (2010): 52C30, 52C10, 52C45, 05C62, 68R10, 60D05, 52A22

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Jetzt informieren
Vorheriges Kapitel Introduction
Nächstes Kapitel The Maximum Number of Tangencies Among Convex Regions with a Triangle-Free Intersection Graph
Fußnoten
1
Aichholzer, personal communication.
 
Literatur
1.
B.M. Ábrego, J. Balogh, S. Fernández-Merchant, J. Leaños, G. Salazar, An extended lower bound on the number of ( ≤ ​ k)-edges to generalized configurations of points and the pseudolinear crossing number of K n . J. Comb. Theor. Ser. A 115, 1257–1264 (2008)MATHCrossRef
2.
B.M. Ábrego, M. Cetina, S. Fernández-Merchant, J. Leaños, G. Salazar, 3-Symmetric and 3-decomposable drawings of K n . Discr. Appl. Math. 158, 1240–1258 (2010)MATHCrossRef
3.
B.M. Ábrego, M. Cetina, S. Fernández-Merchant, J. Leaños, G. Salazar, On ( ≤ ​ k)-edges, crossings, and halving lines of geometric drawings of K n . Discrete Comput. Geom. 48, 192–215 (2012)MathSciNetMATHCrossRef
4.
B.M. Ábrego, S. Fernández-Merchant, A lower bound for the rectilinear crossing number. Graphs Comb. 21, 293–300 (2005)MATHCrossRef
5.
B.M. Ábrego, S. Fernández-Merchant, Geometric drawings of K n with few crossings. J. Comb. Theor. Ser. A 114, 373–379 (2007)MATHCrossRef
6.
B.M. Ábrego, S. Fernández-Merchant, J. Leaños, G. Salazar, The maximum number of halving lines and the rectilinear crossing number of K n for n ≤ 27. Electron. Notes Discr. Math. 30, 261–266 (2008)CrossRef
7.
B.M. Ábrego, S. Fernández-Merchant, J. Leaños, G. Salazar, A central approach to bound the number of crossings in a generalized configuration. Electron. Notes Discr. Math. 30, 273–278 (2008)CrossRef
8.
O. Aichholzer, F. Aurehnammer, H. Krasser, Enumerating order types for small point sets with applications. Order 19, 265–281 (2002)MathSciNetMATHCrossRef
9.
10.
O. Aichholzer, J. García, D. Orden, P. Ramos, New lower bounds for the number of ( ≤ k)-edges and the rectilinear crossing number of K n . Discr. Comput. Geom. 38, 1–14 (2007)MATHCrossRef
11.
O. Aichholzer, J. García, D. Orden, P. Ramos, New results on lower bounds for the number of ( ≤ ​ k)-facets. Eur. J. Comb. 30, 1568–1574 (2009)MATHCrossRef
12.
O. Aichholzer, H. Krasser, The point set order type data base: a collection of applications and results. in Proceedings of the 13th Annual Canadian Conference on Computational Geometry CCCG 2001, Waterloo, Ontario, 2001, pp. 17–20
13.
O. Aichholzer, H. Krasser, Abstract order type extension and new results on the rectilinear crossing number. Comput. Geom. Theor. Appl. 36, 2–15 (2006)MathSciNetCrossRef
14.
J. Balogh, G. Salazar, k-Sets, convex quadrilaterals, and the rectilinear crossing number of K n . Discr. Comput. Geom. 35, 671–690 (2006)MathSciNetMATHCrossRef
15.
W. Blaschke, Über Affine Geometrie XI: Lösung des “Vierpunktproblems” von Sylvester aus der Theorie der geometrischen Wahrscheinlichkeiten. Leipziger Berichte 69, 436–453 (1917)
16.
P. Brass, W. Moser, J. Pach, Research Problems in Discrete Geometry (Springer, New York, 2005)MATH
17.
A. Brodsky, S. Durocher, E. Gethner, The rectilinear crossing number of K 10 is 62. Electron. J. Comb. 8, R23 (2001)MathSciNet
18.
A. Brodsky, S. Durocher, E. Gethner, Toward the rectilinear crossing number of K n : new drawings, upper bounds, and asymptotics. Discr. Math. 262, 59–77 (2003)MathSciNetMATHCrossRef
19.
M. Cetina, C. Hernández-Vélez, J. Leaños, C. Villalobos, Point sets that minimize ( ≤ ​ k)-edges, 3-decomposable drawings, and the rectilinear crossing number of K 30. Discr. Math. 311, 1646–1657 (2011)MATHCrossRef
20.
M.W. Crofton, Probability, in Encyclopedia Britannica, 9th edn. Philadelphia, PA: J. M. Stoddart 19, 768–788 (1885)
21.
R.B. Eggleton, Ph.D. thesis, University of Calgary, 1973
22.
R.K. Guy, Crossing numbers of graphs. Graph theory and applications, in Proceeding Conference, Western Michigan University, Kalamazoo, Mich., dedicated to the memory of J. W. T. Youngs), Lecture Notes in Math., Springer, Berlin, 303, 111–124 (1972)
23.
H.F. Jensen, An upper bound for the rectilinear crossing number of the complete graph. J. Combin. Theor. Ser B 10, 212–216 (1971)MATHCrossRef
24.
H. Krasser, Order Types of Point Sets in the Plane. Ph.D. thesis, Institute for Theoretical Computer Science, Graz University of Technology, Austria, October 2003
25.
L. Lovász, K. Vesztergombi, U. Wagner, E. Welzl, Convex quadrilaterals and k-sets. Towards a theory of geometric graphs. Contemp. Math. (Amer. Math. Soc., Providence) 342, 139–148 (2004)
26.
27.
E. Scheinerman, H.S. Wilf, The rectilinear crossing number of a complete graph and Sylvester’s “four point” problem of geometric probability. Am. Math. Mon. 101, 939–943 (1994)MathSciNetMATHCrossRef
28.
D. Singer, Rectilinear crossing numbers. Manuscript (1971)
29.
J.J. Sylvester, Question 1491, in The Educational Times (London, April 1864)
30.
J.J. Sylvester, Rep. Br. Assoc. 35, 8–9 (1865)
31.
U. Wagner, On the rectilinear crossing number of complete graphs, in Proceedings of the 14th Annual Symposium on Discrete Algorithms (Baltimore, MD, 2003), ACM, New York, 583–588 (2003)
32.
33.
34.
Metadaten
Titel
The Rectilinear Crossing Number of K n : Closing in (or Are We?)
verfasst von
Bernardo M. Ábrego
Silvia Fernández-Merchant
Gelasio Salazar
Copyright-Jahr
2013
Verlag
Springer New York
Buch
Thirty Essays on Geometric Graph Theory

Print ISBN: 978-1-4614-0109-4

Electronic ISBN: 978-1-4614-0110-0

Copyright-Jahr: 2013

DOI
https://doi.org/10.1007/978-1-4614-0110-0_2

Premium Partner

    Bildnachweise